취준/백준
[백준][Python][7562][BFS] 나이트의 이동
puff
2020. 4. 30. 21:42
문제 : https://www.acmicpc.net/problem/7562
7562번: 나이트의 이동
문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ...
www.acmicpc.net
BFS 문제다.
전형적인 길찾기 문제에서 움직이는 위치만 달라진 문제다.
원래 십자모양으로 움직일 때는 dx = [1,-1,0,0], dy=[0,0,1,-1] 이런 식으로 했는데
이 움직이는 숫자만 달라진다.
import sys
from collections import deque
dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [-1, -2, -2, -1, 1, 2, 2, 1]
T = int(sys.stdin.readline())
for _ in range(T):
q = deque()
size = int(sys.stdin.readline())
x, y = [int(i) for i in sys.stdin.readline().split()]
cx, cy = [int(i) for i in sys.stdin.readline().split()]
q.append([x, y, 0])
v = [[False]*size for _ in range(size)]
v[y][x] = True
while q:
tx, ty, tt = q.popleft()
if cx == tx and cy == ty:
print(tt)
break
for i in range(8):
if 0 <= tx+dx[i] < size and 0 <= ty+dy[i] < size and not v[ty+dy[i]][tx+dx[i]]:
q.append([tx+dx[i], ty+dy[i], tt+1])
v[ty+dy[i]][tx+dx[i]] = True