문제

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

풀이 - 1 (다익스트라)

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

리스트 인덱스 범위만 주의해서 풀면 된다.

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)

n,k=map(int,input().split())

distance = [INF] * (100001)
graph = [[] for i in range(100001)]

for i in range(100001):
    if i * 2 <= 100000:
        graph[i] = [(i * 2, 0),(i - 1, 1),(i + 1,1)]
    elif i + 1 <= 100000:
        graph[i] = [(i - 1, 1), (i + 1, 1)]
    else:
        graph[i] = [(i - 1, 1)]

q = []
heapq.heappush(q,(0,n))
distance[n] = 0
while q:
    dist, now = heapq.heappop(q)
    if distance[now] < dist:
        continue
    for i in graph[now]:
        cost = dist + i[1]
        if cost < distance[i[0]]:
            distance[i[0]] = cost
            heapq.heappush(q,(cost,i[0]))

print(distance[k])

풀이 - 2 (0-1 너비 우선 탐색)

다익스트라 알고리즘을 사용해서도 풀 수 있지만, 0-1 너비 우선 탐색이라는 방법을 사용하면 더 빠르게 풀 수 있다.

0-1 너비 우선 탐색은 이름에서도 유추할 수 있는 것처럼, 간선의 가중치가 0 또는 1일 때만 사용할 수 있는 방법이다.

우선 거리 리스트 dist는 매우 큰 숫자로 초기화 해주고, 덱에는 수빈이의 위치인 n을 넣어준다.

그리고 자기 자신까지의 거리는 0 이므로, dist[n] = 0을 해준다.

덱이 빌 때까지 while문을 돈다. while문 안에선 다음과 같은 동작을 해준다.

1. 덱을 popleft 해서 변수 cur에 저장한다.
2. 만약 cur가 동생의 위치인 k와 동일하다면 while문을 탈출한다.
3. 변수 warp에 cur * 2를 저장한다.
4. 만약 warp가 리스트 범위 내에 있고 dist[warp] > dist[cur]라면, 즉 warp까지의 거리를 갱신할 수 있다면 dist[warp] = dist[cur]를 해주고 덱에는 warp를 appendleft 해준다.
5. 변수 left = cur - 1, 변수 right = cur + 1을 저장한다.
6. 만약 left나 right가 리스트 범위 내에 있으면서 거리 정보를 갱신할 수 있다면 거리 정보를 갱신하고 덱에 left나 right를 append 해준다.
7. while 문이 끝나면 dist[k]를 출력한다.

위의 과정을 보면 warp 값은 덱의 왼쪽에, left & right 값은 덱의 오른쪽에 추가해주는 것을 알 수 있다. 그 이유는 warp 위치로 이동하는 경우엔 가중치가 0이고 left & right 위치로 이동하는 경우엔 가중치가 1이므로 가중치가 0인 경우를 먼저 조사하는게 이득이기 때문이다. 변수 cur에는 덱을 popleft 시킨 값을 저장하기 때문에 가중치가 0인 경우는 왼쪽에, 가중치가 1인 경우는 오른쪽에 넣는게 유리하다.

이런 식으로 푸는 방법이 0-1 너비 우선 탐색 알고리즘이다.

import sys
from collections import deque
input = sys.stdin.readline
INF = int(1e9)
n,k=map(int,input().split())

Max = 100000

dist = [INF for i in range(Max + 1)]

dq = deque()

dq.appendleft(n)
dist[n] = 0

while dq:
    cur = dq.popleft()

    if cur == k:
        break

    warp = cur * 2

    if warp <= Max and dist[warp] > dist[cur]:
        dist[warp] = dist[cur]
        dq.appendleft(warp)

    left = cur - 1
    right = cur + 1

    if left >= 0 and dist[left] > dist[cur] + 1:
        dq.append(left)
        dist[left] = dist[cur] + 1
    
    if right <= Max and dist[right] > dist[cur] + 1:
        dq.append(right)
        dist[right] = dist[cur] + 1

print(dist[k])