문제

나의 요약

D 길이의 고속도로를 지난다. 고속도로엔 지름길 존재한다. 지름길은 일방통행이고, 길을 거꾸로 가는 역주행은 불가하다. 이때 운전해야하는 거리의 최솟값을 출력하자.

접근 방법

처음엔 그리디로 접근 가능한지 생각했지만, 지름길마다 길이가 또 다르기 때문에 그리디로 한번에 파악할 수는 없었다. 지름길의 최대 개수가 12개였기 때문에, 연결될 수 있는 지름길을 모두 탐색하더라도 시간적인 문제가 없을 것이라고 판단했다.

한 지름길에 대해서, 연결될 수 있는 지름길들로 가거나, 혹은 여기서 즉시 목적지로 갔을 때의 운전 거리 중 가장 짧은 것을 찾으면, 그것이 그 지름길에서 출발하는 거리의 최솟값이다.

모든 지름길을 대상으로 시작 지름길로 정하고, 이 지름길들에서 출발하는 거리의 최솟값과 그냥 바로 가는 거리 중 가장 짧은 거리를 출력한다.

풀이

#include <bits/stdc++.h>
using namespace std;

int N, D;
vector<pair<pair<int, int>, int>> shortcuts;

void Input()
{
    cin >> N >> D;
    shortcuts.resize(N);

    for(int i = 0; i < N; i++)
    {
        cin >> shortcuts[i].first.first >> shortcuts[i].first.second >> shortcuts[i].second;
    }
}

int DFS(int node, int drive, int prev)
{
    int now = shortcuts[node].first.second;
    drive += shortcuts[node].first.first - prev;
    drive += shortcuts[node].second;

    int minDrive = drive + D - now;
    for(int i = node + 1; i < N; i++)
    {
        if(shortcuts[i].first.first >= now && shortcuts[i].first.second <= D)
        {
            int nextDrive = DFS(i, drive, now);
            minDrive = min(minDrive, nextDrive);
        }
    }
    return minDrive;
}

void Solve()
{
    sort(shortcuts.begin(), shortcuts.end());

    int ans = D;
    for(int i = 0; i < N; i++)
    {
        if(shortcuts[i].first.second <= D)
        {
            ans = min(ans, DFS(i, 0, 0));
        }
    }

    cout << ans;
}

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

    Input();
    Solve();
}

DFS 함수는 (현재 지름길 번호, 지금까지 운전한 거리, 현재 지름길 전의 위치)를 인자로 사용한다. 먼저 현재 지름길에 대해 운전을 진행하고, 이후 이 지름길의 도착 위치보다 출발 위치가 멀리 있는 지름길들로 DFS를 진행한다. 여기서 가장 짧은 거리를 운전한 지름길 또는 도착지까지 바로 간 거리 중 짧은 것을 반환한다.

이를 통해 바로 도착지로 가는 것, 또는 특정 지름길을 처음으로 이용하는 최단 거리 중 가장 짧은 것을 답으로 출력한다.

회고

일단 백트래킹을 이용한 방법으로 해결했다. 작동 시간이 0ms였기 때문에 충분히 효율적인 방법이라고 생각은 한다.
다만 다른 분들의 풀이를 보니, 다이나믹 프로그래밍을 이용해서 풀이한 것이 많았다. DP[i]는 i까지 가는 최소 비용을 나타내고, DP[i-1]에서 1을 더한 값과, i에 도착하는 지름길을 이용한 거리 중 짧은 것으로 DP[i]을 저장한다. 이를 통해 DP[D]를 출력해서 풀이했다.

지금은 지름길의 개수가 많지 않아 백트래킹이 가능했지만, 더 커지거나 하면 다이나믹 프로그래밍으로 푸는 것이 훨씬 효율적이라는 생각이 들었다.