[🥈2 / 백준 7562 / 파이썬] 나이트의 이동

 

7562번: 나이트의 이동

 

문제

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

입력

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

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

출력

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

 

예제 입력  3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1

예제 출력  5 28 0

 

풀이

 

나이트가 목적지까지 가는 데 얼마나 걸리는 지 출력하는 문제이다.

BFS로 나이트가 특정 좌표까지 움직일 수 있는 최단 거리를 구할 수 있다.

 

0으로 채워진 체스판을 만들고 시작점을 기준으로 BFS를 진행한다.

 

해당 좌표값이 0이면 방문하지 않은 것,

1 이상이면 해당 좌표까지 가는 데 걸리는 최소 시간을 의미한다.

 

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

for i in range(int(input())):
    n,deq = int(input()),deque()
    start,end = tuple(map(int,input().split())),tuple(map(int,input().split()))
    board = [[0 for i in range(n)] for i in range(n)]

    deq.append(start)
    # 시작점과 끝점이 같으면 바로 0 출력
    if start == end:
        print(0)
    else:
        # 큐(덱)에 원소가 남아있다면 계속 반복
        while(deq):
            # 답이 구해졌으면 종료
            if board[end[0]][end[1]]:
                break
                
            x,y = deq.popleft()
            # 8방향으로 BFS 진행
            for ap,bp in [-2,1],[-2,-1],[1,2],[-1,2],[2,1],[2,-1],[1,-2],[-1,-2]:
                a = ap+x; b = bp+y
                if n > a >= 0 and n > b >= 0 and board[a][b] == 0:
                    deq.append((a,b))
                    board[a][b] = board[x][y]+1

        print(board[end[0]][end[1]])