[BOJ/Gold 3] 백준 31230 모비스터디(C++)

문제 링크

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

31230번: 모비스터디

 

문제

현대모비스는 글로벌 자동차 부품 기업으로 자율주행, 커넥티비티, 전동화 분야에 역량을 집중해 스마트 모빌리티 시대를 선도하고 있습니다.
현대모비스는 앞으로 미래 모빌리티 산업에서 소프트웨어와 하드웨어를 결합한 차별화된 모빌리티 솔루션을 제공하는 선도기업으로 도약하기 위해 노력하고 있으며, 이러한 연구개발과 생산능력 등 핵심역량을 바탕으로 스마트 모빌리티, UAM, 로보틱스 사업분야로 비즈니스를 확대해 나가고 있습니다.

 

민겸이와 시은이는 이런 꿈의 직장인 현대모비스에 입사하기 위해 모비스터디라는 이름의 스터디를 진행하기로 했다. 하지만, 민겸이와 시은이는 서로 다른 도시에 살고 있기 때문에, 스터디를 진행할 장소를 정해야 한다.

민겸이와 시은이는 1번부터 N번까지 번호가 부여된 N개의 도시와 서로 다른 두 도시를 잇는 M개의 양방향 도로가 있는 나라에 살고 있다. 도로마다 통행하는 데 걸리는 시간이 양의 정수로 존재하고, 각 도시에서 도로를 통해 항상 다른 모든 도시로 이동할 수 있다. 또한, 같은 도시를 출발지와 도착지로 두고 있는 도로는 존재하지 않으며, 임의의 두 도시를 잇는 도로는 최대 1개 존재한다.

민겸이는 A번 도시, 시은이는 B번 도시에 살고 있다. 민겸이는 시은이와 모비스터디를 위해 둘이서 만날 도시를 정하려고 한다. 최단 경로 문제를 풀던 민겸이는 약속 장소를 정할 때, A 도시에서 B 도시까지 이동하는 최단 경로 위에 존재하는 도시로 약속 장소를 정하는 것이 좋다고 생각했다. 이때, 최단 경로가 여러 개라면 그중 하나 위에만 존재해도 된다. A번 도시와 B번 도시 또한 약속 장소가 될 수 있음에 유의하자.

하지만, 민겸이는 이러한 조건을 만족하는 도시가 어디 있는지 모른다. 민겸이는 이 문제를 풀기에는 너무 귀찮았기 때문에, 여러분에게 해결을 부탁했다.

 

입력

첫 번째 줄에 도시의 개수 N과 도로의 개수 M, 민겸이가 살고 있는 도시의 번호 A, 시은이가 살고 있는 도시의 번호 B가 공백으로 구분되어 주어진다. (2 ≤ N ≤ 200,000; 1 ≤ M ≤ 300,000; 1 ≤ A, B ≤ N; A ≠ B)

다음 M개에 줄에 각 도로의 정보를 나타내는 세 정수 a, b, c가 공백으로 구분되어 주어진다. 해당 도로는 a 도시와 b 도시를 양방향으로 잇고 있으며, 통행하는 데 c만큼의 시간이 걸린다. (1 ≤ a, b ≤ N; 1 ≤ c ≤ 10^9; a ≠ b)

입력으로 주어지는 모든 수는 양의 정수다.

 

출력

첫째 줄에 민겸이가 약속 장소로 정할 수 있는 도시의 개수를 출력한다.

둘째 줄에 민겸이가 약속 장소로 정할 수 있는 도시의 번호를 공백으로 구분하여 오름차순으로 출력한다.

 

예제 입력 1

7 8 1 6
1 3 3
1 4 1
4 5 1
5 2 2
2 6 3
1 7 2
7 2 2
3 6 5

예제 출력 1

6
1 2 4 5 6 7

 

 

첫 번째 테스트 케이스에 대한 그림이다. 이 테스트 케이스에는 1 → 7 → 2 → 6 경로와 1 → 4 → 5 → 2 → 6 경로 총 2개의 최단 경로가 존재하며, 최단 경로 위에 존재하는 도시는 1, 2, 4, 5, 6, 7번 도시이다.

예제 입력 2

2 1 1 2
1 2 5

예제 출력 2

2
1 2

 

알고리즘 분류

• 최단 거리 알고리즘

 

풀이

데이크스트라를 한 번 수행하여 A번 도시에서 출발하여 다른 도시까지 도달하는 데 걸리는 최소 시간을 기록하면서, 이전에 어떤 도시를 얼마만큼의 시간이 드는 도로를 거쳐서 왔는지를 따로 기록해둔다.

이후 B번 도시에서부터 A번 도시까지 가는 최단 경로를 추적하기 위하여 DFS를 이용한다. 현재 도시까지 도달하는 데 걸리는 최소 시간과 이전 도시까지 도달하는 데 걸리는 최소 시간의 차가 현재 도시와 이전 도시를 잇는 도로를 이용하는 데 걸리는 시간과 일치하면 이전 도시는 최단 경로에 포함되는 도시인 것이다.

마지막으로 최단 경로에 포함되는 도시의 개수를 출력하고, 다음 줄에 공백을 기준으로 해당 도시들을 출력해준다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <algorithm>
#define MAX 200001
#define INF 2e14
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, A, B, U, V;
LL C;
vector<pair<int, LL> > Edge[MAX];
LL Dist[MAX];
vector<pair<int, LL> > Prev[MAX];
set<int> Answer;

void init() {
    for (int i = 0; i < MAX; i++) {
        Dist[i] = INF;
    }
}

void input() {
    cin >> N >> M >> A >> B;
    for (int i = 0; i < M; i++) {
        cin >> U >> V >> C;
        Edge[U].push_back(make_pair(V, C));
        Edge[V].push_back(make_pair(U, C));
    }
}

void dijkstra() {
    priority_queue<pair<LL, int> > PQ;
    Dist[A] = 0;
    PQ.push(make_pair(0, A));

    while (!PQ.empty()) {
        LL NowC = -PQ.top().first;
        int NowX = PQ.top().second;
        PQ.pop();

        if (Dist[NowX] < NowC) {
            continue;
        }

        for (int i = 0; i < (int)Edge[NowX].size(); i++) {
            int NextX = Edge[NowX][i].first;
            LL NextC = Edge[NowX][i].second;
            if (Dist[NextX] > Dist[NowX] + NextC) {
                Dist[NextX] = Dist[NowX] + NextC;
                PQ.push(make_pair(-Dist[NextX], NextX));
                Prev[NextX].push_back(make_pair(NowX, NextC));
            }
            else if (Dist[NextX] == Dist[NowX] + NextC) {
                Prev[NextX].push_back(make_pair(NowX, NextC));
            }
        }
    };
}

void trace_Path(int NowX, LL Nowc) {
    Answer.insert(NowX);
    if (NowX == A) {
        return;
    }

    for (int i = 0; i < (int)Prev[NowX].size(); i++) {
        int PrevX = Prev[NowX][i].first;
        LL PrevC = Prev[NowX][i].second;
        if (Dist[PrevX] == Dist[NowX] - PrevC) {
            trace_Path(PrevX, Nowc - PrevC);
        }
    }
}

void settings() {
    dijkstra();
    trace_Path(B, Dist[B]);
}

void find_Answer() {
    cout << (int)Answer.size() << "\n";
    for (auto IT : Answer) {
        cout << IT << " ";
    }
    cout << "\n";
}

int main() {
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}