백준 7562번: 나이트의 이동 (파이썬)

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

7562번: 나이트의 이동

 

문제

 

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

 

입력

 

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

 

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

 

출력

 

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

 

풀이

 

미로에서 최단 경로 찾기 문제를 해결하는 것처럼 해결할 수 있다.

최단 경로를 찾아야 하므로 DFS보단 BFS가 적합하며, 이동할 때마다 칸 수를 증가시켜줌으로써 문제를 해결하였다.

 

소스 코드

 

import sys
from collections import deque

t = int(sys.stdin.readline())
dxy = [(1, 2), (2, 1), (-1, 2), (-2, 1), (1, -2), (2, -1), (-1, -2), (-2, -1)]

for _ in range(t):
    l = int(sys.stdin.readline())
    cur_x, cur_y = list(map(int, sys.stdin.readline().split()))
    des_x, des_y = list(map(int, sys.stdin.readline().split()))

    visited = [[False for _ in range(l)] for _ in range(l)]
    q = deque([(cur_x, cur_y, 0)])
    while q:
        x, y, cnt = q.popleft()
        visited[x][y] = True
        if (x, y) == (des_x, des_y):
            print(cnt)
            break

        for dx, dy in dxy:
            if 0 <= x+dx < l and 0 <= y+dy < l and not visited[x+dx][y+dy]:
                visited[x+dx][y+dy] = True
                q.append((x+dx, y+dy, cnt+1))