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

백준 - 7562 나이트의 이동

문제

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

입력

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

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

출력

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

예제

---

알고리즘

1. 나이트의 이동

• 나이트가 움직일 수 있는 방향 8가지를 dx , dy 리스트에 저장
• 방향 이동 ➡️ 현재 x, y 좌표 + dx , dy

2. BFS

• 기존 BFS를 변형시킴
• 나이트가 움직이는 방향에 인접한 정점을 큐에 넣으며 동작

코드

from sys import stdin
from collections import deque

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

def bfs(x, y):
	graph[y][x] = 0
	queue = deque()
	queue.append((x, y))
	while queue:
		x, y = queue.popleft()
		for i in range(8):
			nx = x + dx[i]
			ny = y + dy[i]
			if 0 <= nx < size and 0 <= ny < size and graph[ny][nx] == 0:
				graph[ny][nx] = graph[y][x] + 1
				queue.append((nx, ny))
				if nx == ax and ny == ay:
					break

for _ in range(int(input())):
	size = int(stdin.readline().strip())
	x, y = map(int, stdin.readline().split())
	ax, ay = map(int, stdin.readline().split())
	graph = [[0] * size for _ in range(size)]
	if x == ax and y == ay:
		print(0)
	else:
		bfs(x, y)
		print(graph[ay][ax])