[Python] 백준 / gold / 13549 : 숨바꼭질 3

문제 링크 : https://www.acmicpc.net/problem/13549

0-1 BFS 문제. 이 문제 풀려고 고민 엄청했다.. 이거 내가 아는 알고리즘 선에서는 진짜 풀 수 없다 ; 라고 생각들때까지 고민했는데, 진짜 내가 모르는 알고리즘이어서 다행이었다.

공부해봤는데, 간선 가중치가 0과 1, 두 종류일 경우는 BFS, 다익스트라 알고리즘이 아닌 "0-1 BFS" 알고리즘으로 푸는게 좋다는건 이미 웰노운 이었다. 또 나만 빼고 다 웰노운이지. 심지어 이 유형은 가끔 대기업 계열사 코테에서도 출몰한다고 한다.

BFS 는 queue 를 사용한 알고리즘이라면, 0-1 BFS 는 queue 를 deque 로만 교체해주면 되는 알고리즘이었다. 단, 가중치가 0 인 간선은 dq.appendLeft(x) 로 앞쪽에 삽입해준다.

기억할것 : 0-1 BFS 문제는 deque 로 푼다. 시간 복잡도는 O(V+E) 다.

힙을 사용한 다익스트라가 O(E logV) 라는 걸 생각해보면 매우 빠른 알고리즘이다. 이제 간선 가중치가 0, 1인 문제는 0-1 BFS 로 참교육 해줄꺼다.

파이썬 코드

from collections import deque
import sys
X = 200000
N, K = map(int, sys.stdin.readline().split())
distance = [X] * (X+1)
answer = 0

dq = deque()
dq.append((N, 0))
distance[N] = 0

while dq:
    now, d = dq.popleft()

    if 0 <= (2 * now) <= X and distance[2 * now] > d:
        dq.appendleft((2 * now, d))
        distance[2 * now] = d

    if 0 <= (now + 1) <= X and distance[now + 1] > d + 1:
        dq.append((now + 1, d + 1))
        distance[now + 1] = d + 1

    if 0 <= (now - 1) <= X and distance[now - 1] > d + 1:
        dq.append((now - 1, d + 1))
        distance[now - 1] = d + 1

print(distance[K])