백준 1446번 지름길 (C++)

문제 링크 : https://www.acmicpc.net/problem/1446

1446번: 지름길

문제 요약

 

1.  세준이는 0에서 D킬로미터 길이의 고속도로를 지나 학교를 간다.

2. N개의 지름길 정보가 주어진다.

3. 세준이가 학교에 가기 위해 운전해야 하는 거리의 최솟값을 구해라.

4. 단, 모든 길은 일방통행이고 고속도로를 역주행할 수는 없다.

 

핵심 포인트

 

이 문제에서 주의해야할 점은 문제 요약의 4번입니다.

모든 길은 일방통행이고 고속도로를 역주행할 수는 없다.

만약 목적지 D가 150km인데 지름길을 통해 151km에 도착한다고 하면, 이 지름길은 사용할 수 없습니다.

예시로 주어진 값중 151km의 지름길은 사용이 불가능하다.

 

문제 풀이

 

1. 필요한 변수를 선언하고 값을 입력받습니다.

int n,d,from,to,dis;
    cin >> n >> d;
    vector<int> map(d+1,MAX); // 목적지까지 최단 거리를 저장할 배열
    vector<pair<int,int>> sc[10001]; // 지름길을 저장할 2차원 pair<int,int> 벡터
    for(int i=0; i<n; i++){
        cin >> from >> to >> dis;
        sc[to].push_back({from,dis});
    }

(1) map 배열은 최대값 MAX로 초기화합니다.

(2) N은 12개 이하로 주어지므로, 위 코드처럼 10001이 아닌 12로 사이즈를 잡아도 무방합니다.

(3) sc배열에 값을 저장할 경우, 출발지점이 아닌 도착지점에 {출발지점, 거리} 쌍을 저장합니다.

 

2. 최단 거리를 구합니다.

 map[0] = 0; // 1
    for(int i=1; i<=d; i++){ // 2
        if(sc[i].size()==0) map[i] = map[i-1]+1; // 3
        else{
            for(auto v:sc[i]){ // 4 
                map[i] = min(map[i],min(map[i-1]+1, map[v.first]+v.second)); // 5
            }
        }
    }

(1) map[0]은 0으로 저장합니다.

(2) 1부터 목표지점 d까지 for문을 진행합니다.

(3) 만약 sc[i]의 사이즈가 0일 경우, 해당 위치에는 지름길이 없다는 뜻입니다. 이 경우 map[i] = map[i-1]+1로 저장합니다.

+1이 되는 이유는 바로 앞의 위치보다 1km를 더 달려서 현재 지점에 도착하기 때문입니다.

(4) sc[i]의 사이즈가 0이 아닐 경우, 지름길이 존재한다는 뜻입니다. sc[i]의 사이즈만큼 for문을 돌립니다.

(5)  map[i]는 다음 두 단계의 최소값을 구하는 과정을 통해 값이 결정됩니다.

- min(map[i-1]+1, map[v.first]+v.second) -> 바로 앞에서 저장된 누적 거리에서 +1한 거리와 VS 지름길의 출발 지점에 저장된 누적거리에서 지름길을 통해 이동한 거리. 이 2가지중 최단 거리를 최소값으로 저장합니다.

- main(map[i], 바로 위에서 저장된 최소값) -> map[i]로 최소값을 또 한번 구하는 이유는, 만약 sc[i]의 지름길 갯수가 2개일 이상일 경우를 대비하기 위함입니다.

 

3. 답을 출력합니다.

cout << map[d] << "\n";

 

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 987654321

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,d,from,to,dis;
    cin >> n >> d;
    vector<int> map(d+1,MAX);
    vector<pair<int,int>> sc[10001];
    for(int i=0; i<n; i++){
        cin >> from >> to >> dis;
        sc[to].push_back({from,dis});
    }
    map[0] = 0;
    for(int i=1; i<=d; i++){
        if(sc[i].size()==0) map[i] = map[i-1]+1;
        else{
            for(auto v:sc[i]){ // 8 - 2 - 3
                map[i] = min(map[i],min(map[i-1]+1, map[v.first]+v.second));
            }
        }
    }
    cout << map[d] << "\n";
    return 0;
}