[백준 Python] 1446번 지름길

백준 파이썬 1446번 지름길

Silver 1

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

dp, 다익스트라 두가지 유형으로 풀 수 있는 문제이다.

1️⃣ DP

import sys
input = sys.stdin.readline
n, d = map(int, input().split())
graph = []
dp = [i for i in range(d+1)]
for _ in range(n):
    start, end, dist = map(int, input().split())
    #제외 조건
    if end > d: continue #고속도로 역주행 불가
    if end-start < dist: continue #지름길의 길이가 긴 경우
    graph.append((start, end, dist))
#start 기준으로 정렬을 시켜 dp[start]가 최소 거리로 갱신될 수 있게 해준다.
graph.sort()
for i in range(d+1):
    if i > 0:
        dp[i] = min(dp[i], dp[i-1]+1) #고속도로
    for start, end, dist in graph:
        if start == i:
            dp[end] = min(dp[end], dp[start]+dist) #지름길 이용
print(dp[d])

2️⃣ 다익스트라

import sys, heapq
input = sys.stdin.readline
n, d = map(int, input().split())
graph = {i:[] for i in range(d+1)}
for i in range(d):
    graph[i].append((i+1, 1)) #end, cost 고속도로 이용
for _ in range(n):
    start, end, dist = map(int, input().split())
    #제외 조건
    if end > d: continue
    if end-start < dist: continue
    graph[start].append((end, dist))
distance = [float('inf')] * (d + 1)
distance[0] = 0
heap = [(0, 0)]
while heap:
    dist, now = heapq.heappop(heap)
    if distance[now] < dist: continue
    for nxt, cost in graph[now]:
        new_dist = cost + dist
        if new_dist < distance[nxt]: #새로운 경로의 dist가 더 작은 경우
            distance[nxt] = new_dist
            heapq.heappush(heap,(new_dist, nxt))
print(distance[d])