백준 1446번 지름길

문제 해석

매일 차를 타고 Dkm 길이의 고속도로를 지나는데 지름길이 존재하는 것을 발견

1. 지름길의 개수 N / 고속도로의 길이 D (1 <= N <= 12, 1 <= D <= 10000)
2. N 개의 줄 각각에 1 <= {시작 위치, 도착 위치, 지름길의 길이} <= 10000 생성
3. 시작위치 < 도착위치

5 150
0 50 10
0 50 20
50 100 10
100 151 10
110 140 90

기존 길이 : max_length = 150 보다 크면 안됨
=> (도착위치 - 시작위치) + .. <= 150

벨만-포드 알고리즘으로 노드 x에서 다른 노드로 가는 최단 경로를 구하는 코드임 먼저, 간선 리스트를 생성하고 매 라운드 마다 모든 간선을 살펴보며 그 간선이 거리를 줄이는데 사용되는지 확인할 수 있다. 총 n-1의 라운드로 구성이 되어 있다. 그리고 사이클이 없는 그래프이므로 동적계획법을 적용해서도 풀 수 있다.

조건

1. 최종 도착위치는 항상 150 이상이다.
2. 도착위치가 150 이상이 되는 경로의 길이 중 가장 작은 것을 구해야 한다.
3. 기존 n Km를 도달하는데 경로의 길이는 n 이다.

최종 코드

# N과 D 입력
N, D = map(int, input().split())

road_list = [i for i in range(0, 10000)]
road_dict = {}

for i in range(0, N):
    start, end, length = map(int, input().split())
    road_dict[i] = [start, end, length]

for i in range(0, D+1):
    if i > 0:
        road_list[i] = min(road_list[i], road_list[i-1] + 1)
    for val in road_dict.values():
        if i == val[0] and val[1] <= D and road_list[i] + val[2] < road_list[val[1]]:
            road_list[val[1]] = road_list[i] + val[2]

print(road_list[D])