[골드 5] 백준 13549 - 숨바꼭질 3 (파이썬)

https://www.acmicpc.net/problem/13549

풀이

다익스트라 알고리즘을 이용해서 풀 수 있다.

이 문제는 가중치가 0 또는 1인 그래프에서 최단 시간을 구하는 문제이다.

문제를 확인하면 다음과 같은 정보를 확인 할 수 있다.

• 수빈이는 현재 위치 N, 동생의 위치는 K이다.
• 수빈이는 다음 3가지 방법으로 이동 가능하다.
  • x - 1 = 1초
  • x + 1 = 1초
  • 2 * x = 0초

즉, 0초짜리 이동이 존재하는 가중치 0과 1의 그래프이므도, 일반 BFS보다는 0-1 BFS 또는 다익스트라가 적합하다.

adj = [[] for _ in range(200001)]

문제에서 최대 위치가 200000이므로, 0부터 200000까지 정점으로 보고 인접 리스트를 초기화한다.

범위를 넉넉하게 잡은 이유는 2 * X 가 최대 200000까지 될 수 있기 때문이다.

for i in range(200001):
    if i > 0:
        adj[i].append((i - 1, 1))  # X-1 : 1초
    if i < 200000:
        adj[i].append((i + 1, 1))  # X+1 : 1초
    if 2 * i <= 200000:
        adj[i].append((2 * i, 0))  # 2X : 0초

X - 1, X + 1, 2 * X일때의 상황을 고려하여 다음과 같은 조건을 정의했다.

dist = [1e9] * (200001)  # 거리 배열 초기화
pq = PriorityQueue()
pq.put((0, N))  # 시작점 거리 0
dist[N] = 0

다익스트라 알고리즘을 정의한다. 우선 순위 큐를 이용해서 (거리, 현재 위치) 형태로 삽입한다.

d ≠ dist[u] 인 경우는 더 나은 경로가 이미 처리되었으므로 continuce한다.

while pq.qsize() != 0:
    d, u = pq.get()

    if d != dist[u]:
        continue

    for v, w in adj[u]:
        if dist[v] > dist[u] + w:
            dist[v] = dist[u] + w
            pq.put((dist[v], v))

2 * x 경로는 가중치가 0이므로, 먼저 우선순위 큐에 들어가서 확장된다.

이로 인해서 최단시간을 보장할 수 있다.

아마 0-1 BFS로 풀면 더 효울적인것 같은데, 아직 내 수준은 부족한것 같다..

코드

# 백준 13549 - 숨바꼭질 3
# 분류 - 그래프, 다익스트라

from queue import PriorityQueue

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

adj = [[] for _ in range(200001)]

for i in range(200001) :
    if i > 0 :
        adj[i].append((i - 1, 1))
    if i < 200000 :
        adj[i].append((i + 1, 1))
    if 2 * i <= 200000 :
        adj[i].append((2 * i, 0))

# 다익스트라 시행
dist = [1e9] * (200001)
pq = PriorityQueue()
pq.put((0, N))
dist[N] = 0

while pq.qsize() != 0 :
    d, u = pq.get()

    if d != dist[u] :
        continue

    for v, w in adj[u] :
        if dist[v] > dist[u] + w :
            dist[v] = dist[u] + w
            pq.put((dist[v], v))

print(dist[K])