[BOJ] Q1446 지름길

[BOJ] Q1446 지름길

Question

Language: Python

Difficulty: Silver 1

해당 문제의 경우 목적지까지 도달하기 까지의 최단 거리를 구하기 위한 문제로 동적 프로그래밍을 활용하는 방식과 다이직스트라 알고리즘을 활용하는 방식이 존재한다.

Solution 1

DP의 경우 코딩테스트_공부문제와 유사한 방식으로 접근해서 문제를 풀이할 수 있다. 각각의 index(좌표)점들에 대해 지름길을 구하고, 지름길을 갔을 때와 가지 않았을 때를 비교해서 최솟값을 저장한다

i 번째 좌표에서 i+1 번째의 좌표를 도달하기 위한 비용은 항상 1이지만, i+1 번째에 연결된 지름길이 있을 수 있으므로 이 둘을 서로 비교해서 최솟값을 저장한다.

from math import inf
from collections import defaultdict
def solution():
    distances=[inf] * (d+1)
    distances[0]=0

    shortcut_index=defaultdict(list)
    
    #index 별로 지름길을 저장
    for start,end,distance in shortcuts:
        shortcut_index[start].append((end,distance))
    #각 좌표에 대해 다음 좌표 까지의 최단 거리를 구하는 작업
    for i in range(d):
        distances[i+1]=min(distances[i+1],distances[i]+1)
        for end,distance in shortcut_index[i]:
            if end > d:
                continue
            distances[end]=min(distances[end],distances[i]+distance)


    print(distances[d])

if __name__ =="__main__":
    n,d=map(int,input().split())
    shortcuts=[list(map(int,input().split())) for _ in range(n)]
    solution()

Solution 2

각각의 좌표점들을 노드로 생각하고, 각 노드 i는 노드 i+1과 서로 연결되어 있다. 또한 추가적으로 지름길을 형성하는 노드들간에 간선이 존재하며 이를 활용하여 목적지 노드까지의 최단 경로를 다이직스트라 알고리즘을 통해 구할 수 있다.

from math import inf
from heapq import heappush,heappop
def solution():
    distances=[inf]*(d+1)
    heap=[(0,0)]
    distances[0]=0

    graph=[[] for _ in range(d+1)]

    for start,end,distance in shortcuts:
        if start >=d:
            continue
        graph[start].append((end,distance))

    while heap:
        cost,vertex=heappop(heap)

        if distances[vertex] < cost:
            continue
               
        distances[vertex]=cost

        if vertex ==d:
            break

        for adj_vertex,weight in graph[vertex]:
            if adj_vertex > d:
                continue
            if distances[adj_vertex] > distances[vertex]+weight:
                distances[adj_vertex]=distances[vertex]+weight
                heappush(heap,(distances[adj_vertex],adj_vertex))

             
        heappush(heap,(distances[vertex]+1,vertex+1))

    print(distances[d])

if __name__ =="__main__":
    n,d=map(int,input().split())
    shortcuts=[list(map(int,input().split())) for _ in range(n)]
    solution()