[백준 13549] 숨바꼭질 3 python 파이썬

13549번 - 숨바꼭질 3

문제 이해

1차원 좌표계(수직선) 상의 점 X에서 X+1 또는 X-1로 1초에 이동이 가능하고, 2*X로 0초에 이동이 가능할 때,
주어진 좌표 N에서 출발해 K까지 가는 최단 시간을 구하는 문제.

접근

가중치가 같은 경우라면 BFS로 접근하지만, 가중치가 다른 그래프의 경우는 다익스트라를 통해 최단경로를 구할 수 있다.
가중치가 0, 1 두가지인 경우, 0-1 BFS를 사용할 수도 있다.
참고 - JusticeHui님의 0-1 BFS

ElogE 또는 ElogV의 시간복잡도를 갖는 다익스트라에 비해, 0-1 BFS는 O(V + E)로 조건이 갖추어진다면 더 빠르게 해결이 가능하다.

이 문제에서 직접 제출한 후 확인한 결과, 다익스트라는 324ms, 0-1 BFS는 160ms로 0-1 BFS가 확연히 빠른 실행시간을 보여준다.

정답 코드

다익스트라

import heapq
import sys
input = sys.stdin.readline
def getInts(): return map(int, input().split())


N, K = getInts()
board = [0]*100001
board[N], board[K] = 1, 2
dist = [1e9]*100001
dx = [lambda x:x-1, lambda x:x+1, lambda x:x*2]
dt = [1, 1, 0]


def Dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0
    while q:
        curD, curP = heapq.heappop(q)
        if dist[curP] < curD:
            continue
        for i in range(3):
            nx = dx[i](curP)
            nd = curD + dt[i]
            if nx < 0 or nx > 100000:
                continue
            if dist[nx] > nd:
                dist[nx] = nd
                heapq.heappush(q, (nd, nx))


Dijkstra(N)
print(dist[K])

0-1 BFS

from collections import deque
import sys
input = sys.stdin.readline
def getInts(): return map(int, input().split())


MAX = 100000

INF = int(1e9)
N, K = getInts()
dist = [INF]*(MAX+1)
dq = deque()
dq.append(N)
dist[N] = 0
while dq:
    x = dq.popleft()
    if x == K:
        break
    jump = x*2
    if jump <= MAX and dist[jump] > dist[x]:
        dist[jump] = dist[x]
        dq.appendleft(x*2)
    for dx in [-1, 1]:
        nx = x + dx
        if 0 <= nx <= MAX and dist[nx] > dist[x] + 1:
            dq.append(nx)
            dist[nx] = dist[x] + 1
print(dist[K])