[Python] BOJ 13549 - 숨바꼭질 3

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

13549번: 숨바꼭질 3

# '숨바꼭질' 문제와 다르게 순간이동을 할때는 시간이 0초가 걸린다.

   가중치가 다른 문제에서는 단순 BFS를 돌리면 안된다.

   따라서, 가중치에 우선순위를 사용한 BFS를 사용하거나 다익스트라 알고리즘을 사용하면 된다.

   (나는 다익스트라를 사용했다.)

 

# 처음에 N위치에서 출발하므로 start에 N을 넣고 dijkstra를 돌린다.

   

  - dijkstra함수: q의 원소를 pop해주고, 현재 위치가 목적지 K이면, 걸린시간을 출력하고 break해준다.

                       현재 위치까지 걸린시간이 기존에 걸린시간보다 크면 continue를 해준다.

                         

                       다음 위치의 경우의 수는 (x*2, x+1, x-1) 세 가지뿐이므로 new_destination에

                       이 세 가지 경우를 넣어주고 확인해주면 된다.

                       다음 위치가 0 미만이거나 10만을 넘어가면 무조건 시간이 더 걸리게 되어있다.

                               (K가 0부터 10만 사이에 존재하기 때문에)

                       따라서 new_destination이 0과 10만사이에 존재하고 다음목적지까지 걸린 시간이

                       현재 시간보다 크다면 값을 갱신해준다.

 

                        new_destination = cur_destination*2이면 순간이동을 했으므로

                                 times[new_destination]에 현재시간을 그대로 넣어주고 q에 넣어준다.

                        나머지 경우는 1초가 더 걸리므로

                                 times[new_destination]에 현재시간+1을 넣어주고 q에 넣어준다.

 

import heapq

def dijkstra(start):
    times = [float('inf')] * 200001
    times[start] = 0
    heapq.heappush(q, (times[start], start))

    while q:
        time, cur_destination = heapq.heappop(q)    # time = 현재위치까지 걸린시간
        if cur_destination == K:    # 현재 위치가 목적지 K이면, 시간 출력하고 종료
            print(time)
            break

        if times[cur_destination] < time:    # 기존에 있는 시간보다 길다면 continue
            continue

        for new_destination in (cur_destination*2, cur_destination+1, cur_destination-1):
            if  0 <= new_destination < 100001 and time < times[new_destination]:
                if new_destination == cur_destination*2:
                    times[new_destination] = time   # 순간이동은 0초 걸리므로
                    heapq.heappush(q, (times[new_destination], new_destination))
                else:
                    times[new_destination] = time + 1  # 나머지는 1초 걸리므로 time에 1추가
                    heapq.heappush(q, (times[new_destination], new_destination))

N, K = map(int,input().split())
q = []
dijkstra(N)

(solved.ac 티어: 골드 5)

 

========================================================================

BFS풀이: 추후에 풀 예정