[파이썬] 백준 알고리즘 No.16948 데스 나이트

https://www.acmicp.net/problem/16948 

from collections import deque
n = int(input())
a = [[False] * (n + 1) for _ in range(n + 1)]
r1, c1, r2, c2 = map(int, input().split())
dx = [-2, -2, 0, 0, 2, 2]
dy = [-1, 1, -2, 2, -1, 1]

queue = deque()
queue.append((r1, c1, 0))
while queue:
    x, y, count = queue.popleft()
    a[x][y] = True
    if (x, y) == (r2, c2):
        print(count)
        exit()

    for i in range(6):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and not a[nx][ny]:
            queue.append((nx, ny, count + 1))
            a[nx][ny] = True

print(-1)

 

 

 

이동경로가 많아졌을 뿐, bfs의 큰 틀에서 벗어나진 않은 문제.

count 가중치를 같이 queue에 넣고 돌려 목표점에 도달했을 때 count를 반환해주면 됨.

반환에 실패했을 경우 -1 출력.