[백준] 13549 숨바꼭질 3

🔗 문제 링크

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

💻 코드

import sys
input = sys.stdin.readline 
from collections import deque 

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

def bfs(start):
    dq = deque()
    dq.append((start,0))
    visited = [0] * 200001
    
    while dq:
        x,result = dq.popleft()

        if x == k:
            return result 
            
        for d in range(3):
            if d == 0 and not visited[x*2]:
                nx= x*2
                visited[nx] = 1
                dq.append((nx,result))
            elif d == 1 and not visited[x-1]:
                nx= x-1
                visited[x-1] = 1
                dq.append((nx,result+1))
            else:
                nx = x+1
                visited[x+1] = 1
                dq.append((nx,result+1))

        
print(bfs(n))

🤷‍♂ 풀이

• 간선 가중치가 0 or 1인 경우에 최단 경로를 빠르게 찾기위한 0-1 BFS로 풀었다.

  • 가중치가 0 - 덱의 앞쪽에 추가

  • 가중치가 1 - 덱의 뒤쪽에 추가

• 이 문제에서는 순간이동인 x*2가 가중치 0이 된다.

• 더 견고하게 문제를 풀려면 다익스트라 알고리즘을 사용해야한다.

x-1을 왜 x+1보다 반복문의 우선순위에 둬야할까?

• 최단경로인 -1 * 2보다 +1 +1 이 먼저 도착해 visited를 처리해 뒤따라오는 최단경로를 차단해버린다.

• 0-1 BFS를 사용할 때, 우선순위 큐를 이용한 다익스트라와 달리 최단경로가 반드시 제일 먼저 도착한다는 이론적 뒷받침이 없다.

• x*2를 많이 쓰는 것이 유리한데, 많이 쓰기위해서는 반대되는 -1이 많을수록 유리하다.

• 특정 상황에만 적용되는 임시적이고 직관적인 Adhoc스러운 풀이이다.

그렇다면 dijkstra를 사용한 코드는?

import heapq

def dijkstra(n,k):
    max_size = 200001
    distance = [float('inf')] * max_size 
    distance[n] = 0

    hq = []
    heapq.heappush(hq,(0,n))

    while hq:
        time, x = heapq.heappop(hq)

        if x == k:
            return time 

        nx = x*2
        if 0 <= nx < max_size and time < distance[nx]:
            distance[nx] = time 
            heapq.heappush(hq,(time,nx))

        for nx in [x+1,x-1]:
            if 0 <= nx < max_size and time+1 < distance[nx]:
                distance[nx] = time+1
                heapq.heappush(hq,(time+1,nx))

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

• heap을 사용하면 가장 작은 비용(time)부터 꺼내기에 탐색 순서를 어떻게 하든 영향을 주지 않는다. (x+1, x-1의 순서가 상관이 없다.)