백준 13549 숨바꼭질 3 / python

문제 : 13549

풀이 point

숨바꼭질 문제와 유사하지만
$2 \times n$ 방식에 가중치가 생겼다. n+1, n-1은 1초가 걸리지만 $2 \times n$는 0초가 걸린다.

두 가지 방식으로 풀 수 있다.

1. 다익스트라 알고리즘을 활용하여 가중치를 둔다.
2. 가중치를 Q 삽입 방식으로 둔다.

다익스트라의 경우에는 힙을 활용하여 가중치를 두고 풀 수 있고, 2번째 방식은 $2 \times n$ 방식에 가중치가 있기 때문에 가장 먼저 볼 수 있도록 Q 뒤쪽이 아닌 맨 왼쪽에 삽입해줘서 우선권을 부여해준다. 경우의 수를 보는 if문에도 $2 \times n$를 가장 먼저 보고 항상 Q 앞쪽에 위치할 수 있도록 해야한다.

풀이 코드

1. 다익스트라 방식

import heapq

INF = int(1e9)

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

MAX = 100000

dist = [INF]*(MAX+1)

def dijk():
  pq = []
  dist[N] = 0
  heapq.heappush(pq, (0, N))
  while pq:
    s, n = heapq.heappop(pq)

    if dist[n] < s:
      continue

    if n == K:
      print(dist[K])
      return

    nx = 2*n
    if 0 <= nx <= MAX and dist[nx] > s:
      dist[nx] = s
      heapq.heappush(pq, (s, nx))
    
    nx = n+1
    if 0 <= nx <= MAX and dist[nx] > s+1:
      dist[nx] = s+1
      heapq.heappush(pq, (s+1, nx))
    
    nx = n-1
    if 0 <= nx <= MAX and dist[nx] > s+1:
      dist[nx] = s+1
      heapq.heappush(pq, (s+1, nx))

dijk()

2. 기존 큐 활용 방식

from collections import deque
import sys

N, K = map(int, sys.stdin.readline().split())

MAX = 100000
dist = [-1] * (MAX + 1)
dq = deque()

dist[N] = 0
dq.append(N)

while dq:
    x = dq.popleft()

    if x == K:
        print(dist[x])
        break

    # 0초 이동: 순간이동
    nx = x * 2
    if 0 <= nx <= MAX and dist[nx] == -1:
        dist[nx] = dist[x]
        dq.appendleft(nx)

    # 1초 이동: -1
    nx = x - 1
    if 0 <= nx <= MAX and dist[nx] == -1:
        dist[nx] = dist[x] + 1
        dq.append(nx)

    # 1초 이동: +1
    nx = x + 1
    if 0 <= nx <= MAX and dist[nx] == -1:
        dist[nx] = dist[x] + 1
        dq.append(nx)