백준 1446 - 지름길

문제 설명

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 0부터 D까지 이동하는데 지름길이 존재한다.

지름길은 시작점, 도착점, 지름길의 거리 순으로 정보가 주어진다.

지름길을 이용하여 D에 최소한의 거리를 이동하여 도착하면 된다.

 

처음 문제를 풀었을 때는 우선순위 큐를 이용하여 0에서 D까지 이동하며 거리를 갱신했다.

지름길이 없는 경우도 있으니 현재 지점에서 1씩 더해 다음으로 넘어가는 경로까지 더해주었다.

priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({ 0, 0 });

while (!pq.empty())
{
    auto [cost, current] = pq.top();
    pq.pop();

    if (current == D)
    {
        cout << cost;
        break;
    }

    if (current > D) continue;

    for (auto [end, dist] : shortcuts[current])
    {
        pq.push({ cost + dist, end });
    }

    pq.push({ cost + 1, current + 1 });
}

 

문제를 풀긴했지만 다른 사람들의 코드보다 실행 시간이 많이 나왔다.

 

이를 개선하기 위해, 필요없는 분기를 잘라내는 과정이 필요했다.

따라서, 방문체크를 하여 이미 도착한 곳에서는 다음으로 이동하지 못하게 하였다.

우선순위 큐를 사용하기 때문에 나중에 도착한 루트가 이전에 도착한 루트보다 더 적은 이동거리로 도착할 수 없기 때문이다.

 

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N, D;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> D;

    vector<vector<pair<int, int>>> shortcuts(D);

    for (int i = 0; i < N; i++)
    {
        int start, end, cost;
        cin >> start >> end >> cost;

        shortcuts[start].push_back({ end, cost });
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<bool> visited(D + 1, false);
    pq.push({ 0, 0 });

    while (!pq.empty())
    {
        auto [cost, current] = pq.top();
        pq.pop();

        if (current > D) continue;
        if (visited[current]) continue;
        visited[current] = true;

        if (current == D)
        {
            cout << cost;
            break;
        }

        for (auto [end, dist] : shortcuts[current])
        {
            pq.push({ cost + dist, end });
        }

        pq.push({ cost + 1, current + 1 });
    }

    return 0;
}

---