[Python] 백준 7562 나이트의 이동

7562번: 나이트의 이동

BFS : 나이트가 이동할 경로를 전부 업데이트 하다가 목적지를 만나면 값 출력

 

1) 나이트는 총 8개의 범위를 갈 수 있고 그 경로를 dx와 dy에 저장해 놓고 사용한다.

2) 나이트의 현재 위치가 목적지와 같다면 그 곳의 dp값을 리턴한다.

3) 나이트가 갈 수 있는 방향 8개를 전부 확인하고 나이트가 가지 않았던 위치면 그곳을 탐색한다. 

dp값이 -1 초기값이면 한번도 안갔던 곳이고 dp값을 업데이트 시켜주는데, 이전의 출발 지점의 dp값에 +1 한 값을 넣어주면 된다. 그리고 큐에도 삽입한다.

 

전체 코드

import sys
import collections

input = sys.stdin.readline

dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [-1, 1, -2, 2, -2, 2, -1, 1]


def bfs(cur, des, dp):
    queue = collections.deque([cur])
    dp[cur[0]][cur[1]] = 0
    while queue:
        node = queue.popleft()
        x, y = node[0], node[1]
        if [x, y] == des:
            return dp[x][y]
        for i in range(8):
            a = x + dx[i]
            b = y + dy[i]
            if 0 <= a < I and 0 <= b < I and dp[a][b] == -1:
                dp[a][b] = dp[x][y] + 1
                queue.append([a, b])


T = int(input())
for _ in range(T):
    I = int(input())
    cur_x, cur_y = map(int, input().split())
    des_x, des_y = map(int, input().split())
    dp = [[-1 for _ in range(I)] for __ in range(I)]
    print(bfs([cur_x, cur_y], [des_x, des_y], dp))