[최단 경로] 백준 13549번: 숨바꼭질 3 / 골드5

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

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

import heapq
start, target = map(int, input().split())

visit = []
q = []
heapq.heappush(q, [0, start])
while q:
    time, n = heapq.heappop(q)
    if n == target:
        print(time)
        break
    if n not in visit:
        visit.append(n)
        a = n-1
        b = n+1
        c = 2*n
        if 0 <= a <= 100000:
            heapq.heappush(q, [time+1, a])
        if 0 <= b <= 100000:
            heapq.heappush(q, [time+1, b])
        if 0 <= c <= 100000:
            heapq.heappush(q, [time, c])

bfs + 최단시간 => 다익스트라..!!! 인 것 같지만 유형을 모르고 문제를 만났을 때

다익스트라로 풀어야겠다는 생각을 할 수 있었을 지 아직은 잘 모르겠다.

다익스트라를 너무 안풀어봐서 얼른 적응을 해야할 것 같다.