지름길 ( 1446 번 )

1446번: 지름길

 

---

🧠 알고리즘

• Dijkstra 알고리즘(우선순위 큐를 활용한 최단 경로 탐색)

 

✔️ 동작 방식

• 각 지점을 노드로 보고, 이동 가능한 경로(a → b)와 비용(cost)를 conn 리스트에 저장
• 시작점 0에서 우선순위 큐(heapq)를 사용하여 최단 경로 비용을 누적하면서 탐색
• 현재 노드에서 이동 가능한 다음 노드로의 비용을 계산하고, 기존보다 작으면 업데이트 후 큐에 추가
• 목표 지점 d에 도달하면 최종 최소 비용을 반환

---

 

🧾 코드

import sys
import heapq

def _main(n, d):
    conn = [[(i + 1, 1)] for i in range(d)]
    for _ in range(n):
        a, b, cost = map(int, sys.stdin.readline().rstrip().split())
        if b <= d:
            conn[a].append((b, cost))

    hq = []
    heapq.heappush(hq, (0, 0))

    visit = [float('inf')] * (d + 1)
    visit[0] = 0

    while hq:
        cost, point = heapq.heappop(hq)
        
        for next_point, next_cost in conn[point]:
            use_cost = cost + next_cost
            if visit[next_point] > use_cost:
                visit[next_point] = use_cost

                if next_point == d:
                    break
                    
                heapq.heappush(hq, (use_cost, next_point))
    
    return visit[-1]
    

n, d = map(int, sys.stdin.readline().rstrip().split())
print(_main(n, d))

---

 

⏱️ 시간 복잡도

while hq : 조건 만족시 까지 반복 ( 선형 시간 복잡도 )
	heapq ~ : 내부 heapq 연산 ( 로그 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )