[Python] 백준 1446번 : 지름길

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

1446번: 지름길

---

💡 문제 풀이

다익스트라 문제이다. 그리디로도 풀 수 있을 것 같다.

 

다익스트라 알고리즘을 구현할 줄 알고, 알고리즘을 적용할 노드를 어떻게 설정할지 고민해야 한다.

일반적인 문제와 다르게 특정 노드가 주어지지 않아 고속도로의 길이만큼 노드가 주어졌다고 생각해야 한다.

✔️ 느낀 점

오랜만에 다익스트라 문제를 풀어보기 위해서 쉬운 문제로 갔는데 생각보다 쉽게 접근이 되지 않았다.

파이썬 문법도 낯설어서 조금 애 먹은 것 같다. 대략 한 시간 정도..

처음에는 그리디로 접근했는데 다익스트라로 풀어보려고 했다.

💻 코드

import sys, heapq
input = sys.stdin.readline
INF = int(1e9)

n, d = map(int, input().split())
graph = [[] for _ in range(d+1)]

for i in range(d):
    graph[i].append([i+1, 1])

for _ in range(n):
    start, end, cost = map(int, input().split())
    if end <= d: 
        graph[start].append([end, cost])

distance = [INF] * (d + 1)
distance[0] = 0
queue = []
heapq.heappush(queue, [0, 0])

while queue:
    currentCost, currentNode = heapq.heappop(queue)
    
    if distance[currentNode] < currentCost: continue
    
    for nextNode, nextCost in graph[currentNode]:
        newCost = nextCost + currentCost
        if newCost < distance[nextNode]:
            distance[nextNode] = newCost
            heapq.heappush(queue, [newCost, nextNode])
            
print(distance[-1])