BOJ - 1446

백준 문제 링크
지름길

❓접근법

1. bfs를 사용했다.
2. 지름길의 정보가 있는 리스트 graph,
   0 ~ D까지를 가진 리스트 distance를 만들어준다.
3. i를 0 ~ D+1까지 늘려가며 확인할건데,

• (distance[i], distance[i-1] + 1) 중 작은 값을 distance[i]로 바꿔준다.
• for문으로 graph를 돌면서
  현재 i가 start와 같고, end가 D보다 작거나 같으며,
  distance[i] + 지름길(shortcut) < distance[end]이면
  distance[end] = distance[i] + shortcut으로 바꿔준다.

4. 이 방법으로 한다면 문제의 예시에서 i = 0일 때
   graph를 돌면서 start = 0, end = 50, shortcut = 10
   여기서 distance[0] + shortcut = 10 < distance[end] = 50 이므로
   distance[end] = 10으로 바꿀 수가 있다.
   그러면 distance는 0, 1, 2, 3, .......49, 10, 11 이렇게 바뀔 것이다.
5. 마지막으로 도착지점의 길이를 반환하면 끝!

👌🏻코드

N, D = map(int, input().split())

graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))
    
distance = [i for i in range(D+1)]

for i in range(D+1):
    
    distance[i] = min(distance[i], distance[i-1] + 1)
    
    
    for start, end, shortcut in graph:
        if i == start and end <= D and distance[i] + shortcut < distance[end]:
            distance[end] = distance[i] + shortcut
            
    
print(distance[D])

너무어려웠음...