[BOJ][Python]13549 풀이

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

13549번: 숨바꼭질 3

import heapq
import sys
ssr = sys.stdin.readline

INF = 100001

def dijkstra(n, k): # -1, 1, *2
    h = [(0, n)]
    time = [INF for _ in range(200001)]
    time[n] = 0
    while h:
        cur_time, cur_node = heapq.heappop(h)
        if cur_time > time[cur_node]:
            continue
        if 0 <= cur_node-1 and time[cur_node]+1 < time[cur_node-1]:
            time[cur_node-1] = time[cur_node]+1
            heapq.heappush(h, (time[cur_node]+1, cur_node-1))
        if cur_node+1 <= 100000 and time[cur_node]+1 < time[cur_node+1]:
            time[cur_node+1] = time[cur_node]+1
            heapq.heappush(h, (time[cur_node]+1, cur_node+1))
        if 2*cur_node <= 200001 and time[cur_node] < time[2*cur_node]:
            time[2*cur_node] = time[cur_node]
            heapq.heappush(h, (time[cur_node], 2*cur_node))
    print(time[k])
        
n, k = map(int, ssr().split())
dijkstra(n, k)

예전에 리모컨 문제라고 비슷한 문제를 풀었던 적이 있습니다. 이 문제랑은 약간 다르지만 이 문제에서 간과할 수 있는 부분을 똑같이 함정으로 깔아놨던 문제였어요. 궁금하신 분은 제 블로그의 링크를 올려드릴테니 한 번 보셔도 좋을 것 같네요. https://justduke.tistory.com/66

[BOJ][Python]1107번 풀이

그래서 이 문제에서 주의해야할 부분은 n이 k보다 클 수도 있다는 점과 k보다 큰 값의 위치로 이동해서 -1씩 해서 내려가는게 더 빠른 경우도 있다는 부분이 되겠네요. 예를들어 n = 6000이고 k = 10000이면 처음위치에서 곱하기 2를 한 다음에 2000번 내려가는게 4000번 올라가는 거 보다 빠르겠죠. 그 부분에 유의해서 배열의 사이즈를 정하는 부분이나 조건문을 정하는 부분 등을 잘 체크해보시면 될 것 같습니다.

 

bfs로 푸시는 분들도 있을텐데 메모리 관리만 잘하시고 위에서 말씀드린 주의할 점만 신경쓰신다면 크게 어렵지 않을 것 같습니다.

 

데이크스트라의 개념이 좀 더 궁금하다면,

[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드

[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드