[백준 7562] 나이트의 이동 - Python (BFS)

 

7562번: 나이트의 이동

 

<내 코드>

 

from collections import deque


def bfs(x1, y1, x_end, y_end):

    queue.append([x1, y1])
    done[x1][y1] = 1

    while queue:

        x, y = queue.popleft()

        if (x, y) == (x_end, y_end):
            return (done[x][y] - 1)

        for i in range(8):
            nx = x + move[i][0]
            ny = y + move[i][1]

            if(0 <= nx < n) and (0 <= ny < n) and done[nx][ny] == 0:

                queue.append([nx, ny])
                done[nx][ny] = done[x][y] + 1


case = int(input())

move = [[1, 2], [2, 1], [-1, 2], [-2, 1],
        [1, -2], [2, -1], [-1, -2], [-2, -1]]

for _ in range(case):
    n = int(input())
    start_x, start_y = map(int, input().split())
    end_x, end_y = map(int, input().split())

    done = [[0]*n for _ in range(n)]
    queue = deque()

    # 예외처리
    if start_x == end_x and start_y == end_y:
        print(0)
        continue

    ans = bfs(start_x, start_y, end_x, end_y)
    print(ans)

 

처음에는 min()을 이용해 모든 경우에 대해 최소를 찾으려고 잘 못 생각했다. 역시나 구현이 제대로 안됐다. 

n x n 크기 배열을 만들어 각 지나온 좌표값에 이전 좌표의 값에 +1을 계속해 더해 원하는 지점에 도달했을 때 그때의 값을 출력하면 문제의 정답이 된다. 즉, 현재 지점에서 8방향으로 갈 수 있는 지점을 현재 지점의 값에 +1을 해나가면 되는 것이다.