[PS] BOJ 13549 / 숨바꼭질 3

[PS] BOJ 13549 / 숨바꼭질 3
문제 링크: https://www.acmicpc.net/problem/13549
Thumbnail: Photo by Annie Spratt (Unsplash)

BFS로 풀 수 있는 숨바꼭질 시리즈입니다.

풀이

BFS

역시나 BFS로 풀 수 있습니다. 다만, 이전 숨바꼭질 2(12851)과는 다르게, 순간이동하는 경우는 이전 경우와 시간 차이가 나지 않습니다!

따라서, 순간이동 하는 경우가 다른 경우보다 처리되는 순서가 빨라야 합니다. (우선도가 높아야 합니다.)

전체 코드

from collections import deque
input = open(0).readline
N, K = map(int, input().strip().split())

queue = deque([N])
visited = [-1 for _ in range(200_002)]
visited[N] = 0
while queue:
    current = queue.popleft()
    if current == K:
        print(visited[current])
        break

    for next, time in ((current * 2, visited[current]), (current - 1, visited[current] + 1), (current + 1, visited[current] + 1)):
        if visited[next] == -1 and 0 <= next <= 100_000:
            visited[next] = time
            queue.append(next)
    

solution.py

시행착오

처음에는 다음 탐색할 위치를 +1, -1, \(\times 2\) 순으로 반복했는데, 큐에 추가된 순서의 차이로 인해 순간이동 하는 경우보다 다른 경우가 먼저 처리되는 상황이 발생했습니다.

해당 노드까지 오는데 걸린 시간을 기준으로 우선순위 큐를 사용해도 되지만, 단순히 탐색 순서에서 순간이동을 가장 먼저 큐에 추가해주기만 해도 해결되었습니다.