[BOJ / Python] 지름길

🧩 문제 : 1446 지름길

 

 

---

 

💪🏻 풀이 과정 

 

💡 문제 포인트

1️⃣ 세준이는 0에서 시작, D킬로미터까지 가야한다.

2️⃣ D가 10000보다 작거나 같기 때문에 D까지의 거리 하나하나를 노드로 보면된다.

3️⃣ 노드로 보았을때 일단 최소 거리는 for 문을 통해 1로 초기화해준다. (노드 i 에서 다음 노드 i+1까지의 거리는 1)

4️⃣ 이후 지름길의 정보가 들어오면 graph에 정보를 추가한다. 만약 지름길의 정보에서 지름길이 끝나는지점이 목표지점 D보다 크면 (뒤로 돌아갈 수 없는 고속도로이므로) 정보를 추가하지 않는다.

 

 

💻 코드

import sys
input = sys.stdin.readline
 
N, D = map(int, input().split())
arr = [[] for _ in range(10001)]
for _ in range(N):
    s, e, w = map(int, input().split())
    arr[s].append([w, e])
distance = [i for i in range(D+1)]
 
for i in range(D+1):
    if i != 0:
        distance[i] = min(distance[i], distance[i-1]+1)
    for w, e in arr[i]:
        if e <= D and distance[e] > w + distance[i]:
            distance[e] = w + distance[i]
 
print(distance[D])

 

💭결과