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])