백준7562 나이트의 이동(파이썬)
백준7562 나이트의 이동(파이썬)
문제
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다.
체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, …, l-1} × {0, …, l-1}로 나타낼 수 있다.
둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
출력
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
코드
#나이트의 이동
from collections import deque
import sys
input=sys.stdin.readline
dx=[-2,-2,-1,1,2,2,1,-1]
dy=[-1,1,2,2,1,-1,-2,-2]
def bfs(sx,sy,ex,ey):
q=deque()
q.append([sx,sy])
check[sx][sy]=1
while q:
a,b=q.popleft()
if a==ex and b==ey:
print(check[ex][ey]-1)
return
for i in range(8):
x=a+dx[i]
y=b+dy[i]
if 0<=x<n and 0<=y<n and check[x][y]==0:
q.append([x,y])
check[x][y]=check[a][b]+1
a=int(input())
for _ in range(a):
n=int(input())
sx,sy=map(int,input().split())
ex,ey=map(int,input().split())
check=[[0]*n for i in range(n)]
bfs(sx,sy,ex,ey)
