[백준] 7562번, 나이트의 이동 (Python)

문제

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

7562번: 나이트의 이동

 

코드

import collections

t = int(input())

for i in range(t):
    n = int(input())
    x, y = map(int, input().split())
    rx , ry = map(int, input().split())
    dx, dy = [-1,-2, -1, -2, 1, 2, 1, 2], [2, 1, -2, -1, 2, 1, -2, -1]
    distance = [[0] * n for _ in range(n)]
    
    queue = collections.deque()
    queue.append((x,y))
    
    while queue:
        x,y = queue.popleft()
        if x == rx and y == ry:
            break
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if distance[nx][ny] == 0:
                    distance[nx][ny] = distance[x][y] + 1
                    queue.append((nx,ny))
                    
    print(distance[rx][ry])

나이트 이동하는 방법이 주어진다 8가지 방법을 dx, dy에 넣어주고 distance 배열을 만들어 이동 거리를 계산해준다.

 

queue를 계속 돌다가 x,y가 rx, ry랑 같아지면 while문을 종료하고 도착지 distance[rx][ry]를 출력해주면 된다.