[백준, C++] 1146 - 지름길

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

1446번: 지름길

 

문제 분석

고속도로가 있는데, 고속도로에도 지름길이 있다고 한다(그럼 왜 고속도로지 ?). 아무튼간에, 고속도로를 최단 거리로 주파하고 싶은 문제 속 '세준이' 를 위해 고속도로 출발지점(0)부터 도착지점(D)까지, 지름길을 타든 말든간에 최단 거리가 몇인지를 구해줘야 한다.

 

어떻게 보면 경로에 가중치가 있기 때문에 다익스트라를 사용할 수도 있을 것 같다는 생각을 가장 먼저 하긴 했는데, 잠깐 몇 초 생각하다가 '굳이 ?' 라는 생각이 들었다. 시간 제한이 2초이고, D가 최대 1만인데다 N, 즉 지름길의 개수는 기껏해야 최대 12개이기 때문에 그냥 완전 탐색 + 메모이제이션(DP)으로 풀 수 있다고 생각했기 때문이다(쉬운 길은 쉽게 가라).

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX 10001

using namespace std;

struct PathInfo {
    int endPoint;
    int distance;

    PathInfo(int endPoint, int distance) {
        this->endPoint = endPoint;
        this->distance = distance;
    }
};

int n, d;
int from, to, dist;
vector<PathInfo> paths[10001];
int dp[10001];
int result;

void getInput() {
    cin >> n >> d;
    for (int i = 0; i < n; i++) {
        cin >> from >> to >> dist;
        paths[from].push_back(PathInfo(to, dist));
    }
}

void solve() {
    for (int i = 0; i <= d; i++) {
        dp[i] = MAX;
    }
    dp[0] = 0;

    for (int i = 0; i < d; i++) {
        // 지름길이 있다면 가본다.
        for (int j = 0; j < paths[i].size(); j++) {
            PathInfo pi = paths[i][j];
            dp[pi.endPoint] = min(dp[pi.endPoint], dp[i] + pi.distance);
        }

        // 지름길이 없다면 그냥 간다.
        dp[i + 1] = min(dp[i + 1], dp[i] + 1);
    }

    result = dp[d];
}

void printResult() {
    cout << dp[d] << "\n";
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    getInput();
    solve();
    printResult();

    return 0;
}

 

코드 설명

정말 간단하긴 하다. vector<PathInfo> paths[i] 에 지름길의 정보를 저장한다. 여기서 i는 지름길의 시작 지점을 의미한다.

 

그리고 고속도로의 시작 지점부터 종료 지점 직전까지, for문을 통해 순회한다. 이 과정에서 현재 지점에서 지름길이 있다면 가보고, 지름길의 종점에다가 시작점부터 그 지점까지의 총 거리를 min() 메서드를 통해 최소값을 집어넣는다. 그리고 지름길이 없을 경우까지 고려해 그냥 다음 지점(+ 1 위치)을 지름길 없이 그냥 고속도로로 간다고 쳐서, 또 min() 메서드를 통해 최소값을 집어넣는다.

 

어차피 고속도로의 길이는 최대 1만이고, 지름길은 최대 12개이기 때문에 많아야 1만 12번의 경우만 체크하면 된다.