[백준] 13549번 문제, 숨바꼭질 3

알고리즘

경로를 찾는 문제에서는 다익스트라가 최고라고 하지만 가중치 0과 가중치 1만 있는 그래프에서는 0-1 너비 우선 탐색이 더 좋은 성능을 보여준다.
실제로 다익스트라는 시간복잡도 $O(ElogE)$ 또는 $O(VlogV)$를 가지지만, 0-1 너비 우선 탐색의 경우 시간복잡도 $O(V+E)$을 가진다.
0-1 너비 우선 탐색을 코드로 구현하기 위해 다섯 가지 프로세스를 따라야하며, deque를 사용한다.

1. deque의 front에서 현재 노드를 꺼낸다.
2. 현재 노드 기준 연결된 인접 노드를 확인한다.
3. 현재 노드에서 인접 노드까지 소비되는 가중치가 0이면 $front$로, 가중치가 1이면 $back$으로 추가한다.
4. 현재 노드까지 오는데 소비된 시간 $+$ 인접 노드까지 소비되는 시간을 저장
5. deque에 아무것도 없을 때까지 위의 과정을 반복한다.

코드

import sys
from collections import deque

IN = sys.stdin.readline

if __name__ == "__main__":
    N, K = map(int, IN().split())
    visited = [False for _ in range(100001)] # K 최대값만큼 배열 생성
    visited[N] = True
    que = deque([(N, 0)]) # (node, time)

    if N == K: # 예외처리
        print(0)
        que = []

    while que:
        node, time = que.popleft()

        for next_node, next_time in [(node*2, 0), (node+1, 1), (node-1, 1)]: # *+-
            if next_node >= len(visited) or next_node < 0:
                continue

            if next_node == K: # K에 도달했다면, 프로그램 종료
                print(time + next_time)
                que = []
                break

            if next_time == 1 and not visited[next_node]: # 가중치가 1이면 back에 추가
                que.append((next_node, time + next_time))
            elif next_time == 0 and not visited[next_node]: # 가중치가 1이면 front에 추가
                que.appendleft((next_node, time + next_time))

            visited[next_node] = True