[C++][백준 31230] 모비스터디

문제

#

접근 방법

최단으로 가는 경로를 출력해 주는 문제이다.

A에서 모든 정점까지의 최단 경로를 구한 뒤 B에서 시작하여 A까지의 최단 경로를 추적해 주면 된다.

추적하는 기준은 최단 경로에 쓰인 정점에서 다른 정점까지가 최단 경로라면 두 정점 사이의 간선의 가중치만큼의 차이가 날 것이다. 만약 더 큰 차이가 난다면 해당 정점이 아닌 다른 정점이 최단 경로로 선택된 것이라는 뜻이다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using ll = long long;
using pli = pair<ll, int>;
vector<vector<pli>> graph;
vector<vector<int>> returnPath;
vector<ll> dist;
vector<int> path;
vector<bool> isVisited;
int N, M, A, B;
void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M >> A >> B;

    graph = vector<vector<pli>>(N + 1, vector<pli>());
    dist = vector<ll>(N + 1);
    isVisited = vector<bool>(N + 1);
    returnPath = vector<vector<int>>(N + 1, vector<int>());

    int a, b, c;
    while (M--)
    {
        cin >> a >> b >> c;
        graph[a].push_back({c, b});
        graph[b].push_back({c, a});
    }
}
void dijkstra()
{
    priority_queue<pli, vector<pli>, greater<pli>> pq;

    isVisited[A] = true;
    pq.push({0, A});

    while (!pq.empty())
    {
        pli cur = pq.top();
        pq.pop();

        if (dist[cur.second] < cur.first)
        {
            continue;
        }

        for (pli next : graph[cur.second])
        {
            if ((isVisited[next.second] == false) || (dist[cur.second] + next.first < dist[next.second])) // 방문 안 했거나 현재 값이 더 낮은 경우
            {
                returnPath[next.second].clear();
                returnPath[next.second].push_back(cur.second);
                isVisited[next.second] = true;
                dist[next.second] = dist[cur.second] + next.first;
                pq.push({dist[next.second], next.second});
            }
            else if (dist[cur.second] + next.first == dist[next.second])
            {
                returnPath[next.second].push_back(cur.second);
            }
        }
    }
}
void findPath()
{
    queue<int> q;

    isVisited[B] = false;
    q.push(B);
    path.push_back(B);

    while (!q.empty())
    {
        int cur = q.front();
        q.pop();

        for (int next : returnPath[cur])
        {
            if (isVisited[next] == true) // 재방문 안 했고 현재 값에서 다음 값의 차이가 통행하는데 걸리는 시간인 경우
            {
                isVisited[next] = false;
                path.push_back(next);
                q.push(next);
            }
        }
    }

    sort(path.begin(), path.end());
    cout << path.size() << "\n";
    for (int i : path)
    {
        cout << i << " ";
    }
}
int main()
{
    input();
    dijkstra();
    findPath();
    return 0;
}

풀이

실수로 우선순위 큐의 정렬 기준을 설정 안 해줘서 시간 초과가 났다.
우선순위 큐를 최솟값이 우선되도록 수정해 주었더니 해결됐다.

역추적이 아닌 방법으로도 해결할 수 있다.

A에서 특정 정점까지의 시간하고 B에서 특정 정점까지의 시간의 합이 A에서 B까지의 시간일 경우 A에서 해당 정점을 거쳐서 B까지 도착했다는 뜻이므로 최단 경로의 일부라 할 수 있다.

그러므로 다익스트라를 A, B에서 각각 사용하여 각 정점까지의 최단 시간을 구하고 1부터 N까지 조건을 만족하는지 확인해 주면 된다.