Programming/Algorithm

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

oranz.23 2021. 3. 14. 15:33

문제

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

 

18404번: 현명한 나이트

첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. (

www.acmicpc.net

 

풀이

    움직이는 방식이 일반적인 상하좌우가 아니라 체스의 나이트가 움직이는 방식이라는 점에서 차별화되는 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])