백준 7562. 나이트의 이동

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

1차 시도 코드(실패)

from collections import deque
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(1, T+1):
    N = int(input()) # 체스판 한 변의 길이 (N * N 체스판)
    start_i, start_j = map(int,input().split()) # 나이트가 현재 있는 칸
    end_i, end_j = map(int,input().split()) # 나이트가 이동하려고 하는 칸

    # 나이트는 최소 몇 번만에 이동할 수 있는가?
    ans = 0

    di = [2,1,-2,-1,-1,-2,1,2]
    dj = [1,2,1,2,-2,-1,-2,-1]
    visited = [[0] * N for _ in range(N)]

    def bfs(i,j):
        q = deque([(i,j)])
        visited[i][j] = 1
        while q:
            i, j = q.popleft()
            for w in range(8):
                ni, nj = i+di[w], j+dj[w]
                if ni == end_i and nj == end_j:
                    return
                if 0<=ni<N and 0<=nj<N and visited[ni][nj] == 0:
                    q.append((ni,nj))
                    visited[ni][nj] = visited[i][j] + 1

    bfs(start_i,start_j)
    print(visited[end_i][end_j])

문제

- 첫 칸부터 이동거리를 세고 있기 때문에 (visited[i][j] = 1) 답을 도출할 때 이동거리 -1 해줘야 됨!

- 마지막 두 if문의 순서를 바꿔야 됨(도착해도 이동거리 처리는 해야되기 때문)

+ return문에 visited[ni][nj]를 넣음으로써 print문을 간결하게 쓸 수 있음(두줄->한줄)

피드백 받고 수정한 코드(성공)

from collections import deque
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(1, T+1):
    N = int(input()) # 체스판 한 변의 길이 (N * N 체스판)
    start_i, start_j = map(int,input().split()) # 나이트가 현재 있는 칸
    end_i, end_j = map(int,input().split()) # 나이트가 이동하려고 하는 칸

    # 나이트는 최소 몇 번만에 이동할 수 있는가?
    ans = 0

    di = [2,1,-2,-1,-1,-2,1,2]
    dj = [1,2,1,2,-2,-1,-2,-1]
    visited = [[0] * N for _ in range(N)]

    def bfs(i,j):
        q = deque([(i,j)])
        visited[i][j] = 1
        while q:
            i, j = q.popleft()
            for w in range(8):
                ni, nj = i+di[w], j+dj[w]
                if 0<=ni<N and 0<=nj<N and visited[ni][nj] == 0:
                    q.append((ni,nj))
                    visited[ni][nj] = visited[i][j] + 1
                if ni == end_i and nj == end_j:
                    return visited[ni][nj] - 1

    print(bfs(start_i,start_j))

+ 다시 풀었을 때 풀이

import sys
from _collections import deque

input = sys.stdin.readline

tc = int(input())
for _ in range(tc):
    n = int(input()) # 체스판 한변의길이
    now_x, now_y = map(int,input().split())
    final_x, final_y = map(int,input().split())

    # 최소 몇 번만에 이동할 수 있는지?
    visited = [[0] * n for _ in range(n)]
    def bfs(now_i,now_j):
        q = deque([[now_i, now_j]])
        visited[now_i][now_j] = 1
        while q:
            x, y = q.popleft()
            for di, dj in [[2,1],[1,2],[2,-1],[1,-2],[-2,1],[-1,2],[-1,-2],[-2,-1]]:
                ni, nj = x + di, y + dj
                if 0 <= ni < n and 0 <= nj < n:
                    if visited[ni][nj] == 0:
                        visited[ni][nj] = visited[x][y] + 1
                        q.append([ni,nj])
                    if ni == final_x and nj == final_y:
                        return visited[ni][nj] - 1  # 시작점을 1로 초기화했으므로

    print(bfs(now_x, now_y))

다른 풀이

import sys
from _collections import deque

input = sys.stdin.readline

tc = int(input())
for _ in range(tc):
    n = int(input()) # 체스판 한변의길이
    now_x, now_y = map(int,input().split())
    final_x, final_y = map(int,input().split())
    
    # 시작점과 목표점이 같으면 0 반환
    if (now_x, now_y) == (final_x, final_y):
        print(0)
        continue

    # 최소 몇 번만에 이동할 수 있는지?
    visited = [[0] * n for _ in range(n)]
    def bfs(now_i,now_j):
        q = deque([[now_i, now_j]])
        visited[now_i][now_j] = 1
        while q:
            x, y = q.popleft()
            for di, dj in [[2,1],[1,2],[2,-1],[1,-2],[-2,1],[-1,2],[-1,-2],[-2,-1]]:
                ni, nj = x + di, y + dj
                if 0 <= ni < n and 0 <= nj < n:
                    if visited[ni][nj] == 0:
                        visited[ni][nj] = visited[x][y] + 1
                        if ni == final_x and nj == final_y:
                            return visited[ni][nj] - 1  # 시작점을 1로 초기화했으므로
                        q.append([ni,nj])

    print(bfs(now_x, now_y))