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

문제

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

입력

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

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

출력

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

 

필요한 도구

 

 

1. BFS 알고리즘 - 최소동선을 구해야 하므로 너비우선탐색(BFS)를 이용한다. 방문리스트에 방문이 없을 때만 큐(Queue)에 들어가므로, 방문리스트에 가장 먼저 목적지에 도착한 횟수가 반영된다.

2. dx, dy 좌표 - 나이트의 이동에 맞는 2차원 (x, y) 좌표

 

 

문제해결방법

 

 

1. 위 도구를 활용하여 너비우선탐색(BFS)를 돌린다. BFS는 이동할 수 있는 (x + dx[i], y + dy[i]) 좌표를 모두 큐에 넣고, 깊이우선탐색(BFS)과 다르게 각 깊이의 노드를 순차적으로 돈다. (큐 자료구조에서 먼저 들어간 노드가 빠지므로)

2. 방문리스트에 방문 횟수를 저장한다.

3. 방문리스트에 방문 횟수가 저장되어 있다는 것은 가장 먼저 방문했다는 뜻이므로, 거기에 쓰여진 횟수가 최소값이다.

 

 

- 코드

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def check(x, y):
    return 0 <= x < n and 0 <= y < n

def bfs(x, y):
    q = deque()
    q.append((x, y))
    v[x][y] = 0
    while q:
        x, y = q.popleft()
        if v[ax][ay] != -1:
            return v[ax][ay]
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if check(nx, ny) and v[nx][ny] == -1:
                v[nx][ny] = v[x][y]+1
                q.append((nx, ny))
    return -1

for _ in range(int(input())):
    n = int(input())
    v = [[-1 for _ in range(n)] for _ in range(n)]
    dx = [-2, -2, -1, -1, 1, 1, 2, 2]
    dy = [-1, 1, -2, 2, -2, 2, -1, 1]
    x, y = map(int, input().split())   # 시작지점
    ax, ay = map(int, input().split()) # 도착지점
    print(bfs(x, y))