[백준-16948] 데스 나이트 / Python
카테고리 없음
16948번: 데스 나이트
게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크
www.acmicpc.net
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
r1, c1, r2, c2 = map(int, input().split())
graph = [[0] * n for _ in range(n)]
dx = [-2, -2, 0, 0, 2, 2]
dy = [-1, 1, -2, 2, -1, 1]
def bfs(x, y):
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
for i in range(6):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 0:
graph[nx][ny] = graph[x][y] + 1
if nx == r2 and ny == c2:
return graph[nx][ny]
queue.append((nx, ny))
return -1
print(bfs(r1, c1))
해설
간단하게 해결할 수 있었던 bfs문제!