숨바꼭질 3

백준 13549번: 숨바꼭질 3

아이디어

순간이동을 하는 경우 걸리는 시간이 0이다. 이 경우를 우선적으로 처리해주기 위해 가장 먼저 push한다. 또, 비용이 적은 경우를 우선적으로 처리해주기 위해 우선순위 큐를 이용한다.

코드

import sys
import heapq
input = sys.stdin.readline

N, K = map(int, input().split())
visited = [0] * 100001

def solve(start, end):
    q = []
    heapq.heappush(q, (0, start))
    visited[start] = 1
    while q:
        c, x = heapq.heappop(q)
        if x == end:
            print(c)
            return
        if x * 2 <= 100000 and (visited[x * 2] == 0):
            visited[x * 2] = 1
            heapq.heappush(q, (c, x * 2))
        if x + 1 <= 100000 and (visited[x + 1] == 0):
            visited[x + 1] = 1 
            heapq.heappush(q, (c + 1, x + 1))
        if x - 1 >=0 and (visited[x - 1] == 0):
            visited[x - 1] = 1
            heapq.heappush(q, (c + 1, x - 1))

solve(N, K)

여담

그냥 deque로 풀어도 될듯? 이게 bfs문제에서 한 칸씩 움직일 때 그래프에 숫자 1씩 더해가면서 비용 표시하는 문제가 많아서 자꾸 그렇게 할라다 이상하게 푼다. 비용을 enqueue하는 경우도 생각해봐야겠다.