[백준] 18404번 현명한 나이트 (by Python)

문제

https://www.acmicpc.net/problem/18404

18404번: 현명한 나이트

 

풀이

    움직이는 방식이 일반적인 상하좌우가 아니라 체스의 나이트가 움직이는 방식이라는 점에서 차별화되는 BFS 문제이다. 이에 맞추어 step 리스트를 다르게 바꾸어주었다. 또한, 목적지가 하나가 아님에 따라 하나를 찾을 때마다 체크하고 다 찾은 경우에는 while loop을 탈출하도록 코드를 짜주었다.

 

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [[-1] * (n + 1) for _ in range(n + 1)]
target = [[False] * (n + 1) for _ in range(n + 1)]
ans = []
x, y = list(map(int, input().split()))
for _ in range(m):
    a, b = map(int, input().split())
    ans.append((a, b))
    target[a][b] = True
steps = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
q = deque()
q.append((0, x, y))
arr[x][y] = 0

while m:
    dist, x, y = q.popleft()

    for step in steps:
        nx, ny = x + step[0], y + step[1]
        if 0 < nx <= n and 0 < ny <= n and arr[nx][ny] < 0:
            q.append((dist + 1, nx, ny))
            if target[nx][ny]:
                m -= 1
            arr[nx][ny] = dist + 1

print(*[arr[i][j] for i, j in ans])