알고리즘/백준
[백준] 7562번 나이트의 이동 (파이썬)
알감자
2022. 1. 5. 23:12
7562번: 나이트의 이동
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수
www.acmicpc.net
코드
from collections import deque
T = int(input())
dx = [-1, -2, -1, -2, 1, 2, 1, 2]
dy = [2, 1, -2, -1, 2, 1, -2, -1]
def knight(i, current_x, current_y, want_x, want_y):
tree = list([0 for _ in range(i)] for _ in range(i))
que = deque([])
que.append([current_x,current_y])
tree[current_x][current_y] = 1
while que:
a, b = que[0][0], que[0][1]
que.popleft()
if a == want_x and b == want_y:
return tree[a][b]-1
for j in range(8):
x = a + dx[j]
y = b + dy[j]
if 0 <= x < i and 0 <= y < i:
if tree[x][y] == 0:
que.append([x,y])
tree[x][y] = tree[a][b] +1
for j in range(i):
print(*tree[j])
for _ in range(T):
i = int(input())
current_x, current_y = map(int, input().split())
want_x, want_y = map(int, input().split())
answer = knight(i, current_x, current_y, want_x, want_y)
print(answer)