문제

크기가 N × N인 체스판의 특정한 위치에 하나의 나이트가 존재한다. 이때 M개의 적들의 위치 값이 주어졌을 때, 각 적까지 이동하기 위한 최소 이동 수를 계산하는 프로그램을 작성하시오.

나이트는 일반적인 체스에서와 같이 8가지 방향으로 이동할 수 있다.

풀이

BFS를 사용하여 나이트의 최소 이동 횟수를 구하는 문제이다.

코드

from collections import deque

N, M = map(int, input().split())

dxy = ((1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1))

x, y = map(int, input().split())

enemy_list = [tuple(map(int, input().split())) for _ in range(M)]
result = [0] * M

q = deque([(x, y, 1)])
find_cnt = 0
visited = set([(x, y)])

while q:
    cur_x, cur_y, t = q.popleft()

    for dx, dy in dxy:
        n_x, n_y = cur_x + dx, cur_y + dy
        if (n_x, n_y) in visited:
            continue
        if (n_x, n_y) in enemy_list:
            enemy_idx = enemy_list.index((n_x, n_y))
            if result[enemy_idx] != 0:
                continue
            result[enemy_idx] = t
            find_cnt += 1
        if find_cnt == M:
            break
        q.append((n_x, n_y, t + 1))
        visited.add((n_x, n_y))
    else:
        continue
    break

print(*result)

시간 복잡도

O(N^2)