BOJ 12851 숨바꼭질 2

문제

접근 방법

가중치가 1로 고정되어 있어서 BFS를 사용하면 되지 않을까 하다가 BFS를 사용하면 한번 방문한 곳이 더 짧은 경로로 도달할 수 있음에도 불구하고 visit할 수 없게 될 거 같아서 dijkstra를 사용했다. dijkstra를 사용하면 시작점에서 갈 수 있는 새로운 최단경로가 생길 때마다 다시 탐색을 할 수 있어서 문제에 적합하다고 생각했다.

이때 최단 거리뿐만 아니라 방법 수까지 구해야 해서 ways라는 배열을 따로 만들었다. ways[i]에는 i에 최단거리로 도달할 수 있는 경로 수를 저장한다.

정답 코드

import sys
import heapq
input = sys.stdin.readline

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

"""

n -> k로 최단거리를 구하는것과 같다.

"""

def moves(num):
    return [(1,num-1), (1,num+1), (1,num*2)]

def dijkstra(start):
    q = []
    distances = [sys.maxsize]*(100001)
    ways = [0]*(100001)
    heapq.heappush(q, (0, start))
    distances[start] = 0
    ways[start] = 1
    while q:
        mid_dist, mid_node = heapq.heappop(q)
        if mid_dist > distances[mid_node]:
            continue
        for end_dist, end_node in moves(mid_node):
            if end_node < 0 or end_node > 100000:
                continue
            new_dist = distances[mid_node] + end_dist
            if distances[end_node] > new_dist:
                distances[end_node] = new_dist
                heapq.heappush(q, (new_dist, end_node))
                #최단 거리가 갱신될 떄는 mid_node까지의 경로의 수로 update한다.
                ways[end_node] = ways[mid_node]
            elif distances[end_node] == new_dist:
                #최단 거리로 또 end_node에 도달했을 때는 mid_node까지 왔을 떄의 경로의 수를 더한다.
                ways[end_node] += ways[mid_node]
    return distances, ways

distances, ways = dijkstra(n)
print(distances[k])
print(ways[k])