백준 1446번 C++ 풀이

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

1446번: 지름길

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	실버 1

문제

매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.

세준이가 운전해야 하는 거리의 최솟값을 출력하시오.

입력

첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.

출력

세준이가 운전해야하는 거리의 최솟값을 출력하시오.

---

이 문제는 그래프 입력의 전처리와 이후 최단경로를 구하는 방식 모두 생각해야하는 문제이다.

입력 데이터를 잘 보면, 지름길이라고 입력받은 길의 거리가 그냥 가는거보다 긴 경우도 있고 (예제 입력3의 20 60 45), 
지름길의 도착지점이 D보다 큰 경우(예제 입력1의 100 151 10)는 따지면 안된다. 이 문제는 이러한 입력데이터가 들어오기 때문에 입력받기전 검사를 하는 단계가 먼저 수행되어야 한다.

각 노드간의 거리는 자연수기 때문에, 0번정점부터 D번정점까지 방문하면서, 지름길이 있으면 도착지점의 최단경로를 갱신한다.

순차적으로 탐색을 해보면서 최단경로를 구해주면 된다. 다익스트라의 개념을 응용하는데, i번째 정점에서 지름길로 암만 거리정보를 갱신해봤자, 다음에 방문할 거리가 가장 짧은 정점은 i + 1번 정점이기 때문에, 다익스트라에서 사용하는 우선순위 큐가 필요하지는 않다. 그렇기 때문에, 그냥 순차탐색의 형태로 풀이된다.

 

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
using pii = pair<int, int>;

int N, D;
vector<vector<pii>> graph;

void input() {
    int start, end, len;
    cin >> N >> D;

    graph.resize(D + 1);
    
    for(int i = 0; i < N; i++) {
        cin >> start >> end >> len;
        
        if (len >= end - start) continue;
        if (end > D) continue;

        graph[start].push_back({len, end});
    }
}

void sol() {
    int dist_arr[D + 1];
    fill(dist_arr, dist_arr + D + 1, INF);
   
    dist_arr[0] = 0;
    for(int i = 0; i <= D; i++) {
        if(i) dist_arr[i] = min(dist_arr[i], dist_arr[i - 1] + 1);

        for(auto& elem : graph[i]) {
            dist_arr[elem.second] = min(dist_arr[elem.second], dist_arr[i] + elem.first);
        }
    }

    cout << dist_arr[D];
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    input();
    sol();    
}