[BOJ] 9370 : 미확인 도착지 (C++)

📖 백준 9370번 : https://www.acmicpc.net/problem/9370

조건

시간 제한	메모리 제한
3 초	256 MB

문제

(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)

어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 g와 h 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.

이 듀오는 대체 어디로 가고 있는 것일까?

입력

첫 번째 줄에는 테스트 케이스의 T(1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스마다

• 첫 번째 줄에 3개의 정수 n, m, t (2 ≤ n ≤ 2 000, 1 ≤ m ≤ 50 000 and 1 ≤ t ≤ 100)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
• 두 번째 줄에 3개의 정수 s, g, h (1 ≤ s, g, h ≤ n)가 주어진다. s는 예술가들의 출발지이고, g, h는 문제 설명에 나와 있다. (g ≠ h)
• 그 다음 m개의 각 줄마다 3개의 정수 a, b, d (1 ≤ a < b ≤ n and 1 ≤ d ≤ 1 000)가 주어진다. a와 b 사이에 길이 d의 양방향 도로가 있다는 뜻이다.
• 그 다음 t개의 각 줄마다 정수 x가 주어지는데, t개의 목적지 후보들을 의미한다. 이 t개의 지점들은 서로 다른 위치이며 모두 s와 같지 않다.

교차로 사이에는 도로가 많아봐야 1개이다. m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.

출력

테스트 케이스마다

• 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.

---

풀이

 다익스트라를 적절하게 변형해서 적용하면 풀리는 문제이다. 최단 경로를 탐색할 때, 특정 위치를 지났는지 체크하고 그 값을 유효하게 보존하는 방식으로 풀었다. 주석이 달려있지 않은 부분은 다익스트라를 적용한 부분이라 적당히 넘겨보면 되고 주석이 달려있는 부분이 이 문제를 풀기위해 적절히 변형한 부분이다.

 먼저 다익스트라에서 값이 갱신될 때 g,h 도로를 지났는 지를 체크하는 상태 정보를 0, 1로 표현했다. 시작 노드로 부터 각 노드까지의 최단 거리를 저장하는 dist배열을 pair로 정의하고 second에 상태 정보를 저장했다. first는 그냥 최단 거리를 갖는다. 양방향 그래프이므로 현재 노드와 다음 노드가 g,h 혹은 h,g인 경우 second값을 1로 갱신한다. 값이 갱신되는 지점에서 다음 노드에 대한 dist정보를 현재 노드에 대한 dist 정보로 갱신한다. g,h를 지나온 길은 계속 그 값을 1로 유지한다는 것이다. 만약 g,h를 지나지 않은 길이 최단이면 값이 0이 된다.

 최단 경로가 여러개 존재할 경우 어떻게 처리할 것인지가 가장 중요한 포인트이다. 이 처리가 없다면 g,h를 지나는 최단경로의 상태정보를 갱신해도 다른 최단 경로 때문에 값이 덮어씌워지거나, 거리가 더 작지 않다면 탐색하지 않게 구현을 했을 경우 같은 거리를 갖는 다른 최단 경로들은 애초에 탐색이 될 수도 없을 것이다. 같은 거리를 갖는 다른 최단 경로를 찾았을 때, 상태 정보를 유효하게 보존해야 한다.

 같은 거리를 갖는 다른 최단 경로가 존재할 때, 지나온 길의 second가 1이라면 그 값으로 갱신하고 아닌 경우 현재 second를 유지한다. 이를 통해서 second값이 이미 1일 때 0으로 덮어씌워지지 않게 하고 만약 0이었다면 1로 갱신해서 g,h를 지났는가에 대한 여부를 올바르게 유지한다. 그리고 현재 처리하는 부분이 g,h 도로를 지나는 도중일 수 있으므로 이에 대한 second값 갱신도 해준다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 900000000

using namespace std;

vector <pair<int, int>> dijkstra(int start, int vertex, int g, int h, vector<pair<int, int>> graph[]) {
    //dist 배열에 g,h를 지났는지 체크하는 상태를 second에 저장
    vector<pair<int, int>> dist(vertex + 1, { INF,0 });
    priority_queue<pair<int, int>>pq;

    dist[start].first = 0;
    pq.push({ 0, start });

    while (!pq.empty()) {
        int cur_node = pq.top().second;
        int cur_dist = -pq.top().first;
        pq.pop();

        if (dist[cur_node].first < cur_dist) continue;

        for (int i = 0; i < graph[cur_node].size(); i++) {
            int nxt_node = graph[cur_node][i].first;
            int nxt_dist = cur_dist + graph[cur_node][i].second;

            if (dist[nxt_node].first > nxt_dist) {

                //지나온 길의 second 값을 이어받아서 g,h를 지났는지에 대한 정보를 저장
                dist[nxt_node].second = dist[cur_node].second;
                //g,h 도로를 지나는 중이라면 second값을 1로 갱신
                if ((cur_node == g && nxt_node == h) || (cur_node == h && nxt_node == g)) 
                    dist[nxt_node].second = 1;

                dist[nxt_node].first = nxt_dist;
                pq.push({ -nxt_dist, nxt_node });
            }
            //같은 거리를 가지는 최단경로가 여러개 존재할 경우 g,h를 지나온 길이 있을 때
            //second값이 덮어씌우지지 않도록 처리
            else if (dist[nxt_node].first == nxt_dist) {
                //지나온 길이 g,h를 지나왔다면 1로 갱신, 아니면 현재 second 유지
                if (dist[cur_node].second == 1) dist[nxt_node].second = 1;
                //최단경로인 곳이 g,h 도로를 지나는 중일 수 있으므로 처리
                if ((cur_node == g && nxt_node == h) || (cur_node == h && nxt_node == g))
                    dist[nxt_node].second = 1;
            }
        }
    }
    return dist;
}

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

    int from, to, weight;
    int s, g, h;
    int n, m, t;
    int T;

    cin >> T;
    for (int i = 0; i < T; i++) {
        vector<pair<int, int>> graph[2001];
        int destination[100];
        cin >> n >> m >> t;
        cin >> s >> g >> h;

        for (int j = 0; j < m; j++) {
            cin >> from >> to >> weight;
            graph[from].push_back({ to,weight });
            graph[to].push_back({ from,weight });
        }

        for (int k = 0; k < t; k++) 
            cin >> destination[k];
        
        vector<pair<int, int>>ans = dijkstra(s, n, g, h, graph);
        
        for (int i = 1; i <= n; i++) {
            if (ans[i].second == 1) {
                for (int j = 0; j < t; j++) {
                    if (i == destination[j]) 
                        cout << i << ' ';
                }
            }
        }
        cout << '\n';
    }

    return 0;
}