[백준/C++] 9370 - 미확인 도착지

풀이 시간: 3h02m13s13

시간 복잡도: O((n + m) * log n)

공간 복잡도: O(n + m)

참고 자료

https://www.acmicpc.net/board/view/117492

https://devmath.tistory.com/69

유사 문제

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

문제

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

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

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

예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 6으로 향하고 있다.

입력

첫 번째 줄에는 테스트 케이스의 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(2)와 h(3) 교차로 사이에 있는 도로를 지나갔다고 하였다.

그러나 이 듀오의 출발점은 s = 2이므로 2번에서 출발을 하였고, g가 2이므로, 이 듀오는 g(2)에서 출발하여 h(3)의 방향으로 도로를 지나갔다.

그렇기 때문에 그 다음 최단 경로로 도착할 수 있는 노드는 6번 노드인 것이다. 즉 6번만 목적지 후보에 살아남게 되고, 최단 경로로 도달할 수 없는 5번 노드는 목적지 후보에서 삭제된다.

 

구현 방법

우선 가장 전형적인 다익스트라 알고리즘 방식을 사용하여 최단경로를 구해주는 함수를 다음과 같이 구현하기로 했다.

1. 출발지의 번호와 총 이동거리를 우선순위 큐에 넣어준다.

2. 우선순위 큐는 이동거리가 짧은 순서대로 처리하도록 한다.

3. 현재 정점을 기준으로 인접 노드들을 탐색한다.

4. 이 중 이동거리가 더 짧은 노드가 있을 경우 최단 경로를 갱신해준 후 큐에 넣어준다.

5. 위 과정을 큐가 비어있을 때까지 반복한다.

 

 

그나저나 g와 h는 어떻게 처리해야 하는 걸까.. 🧐

일단 g와 h는 둘 다 거쳐야하는 노드이다. 그렇게 된다면 g와 h를 거치는 경로가 최단경로여야 한다는 것인데,,,,

도무지 본인 머리로는 아이디어가 떠오르지 않아 참고 코드를 보면서 문제를 다시 풀어보았다. 😢

 

보아하니, 크게 2가지 방식 정도가 존재하는 것 같았다.

 

1. g와 h를 기준으로 출발지 s부터 목적지 i까지를 3개의 구간으로 나누어 최단 경로 구하기

우선 목적지를 i라고 하자. 여기서 말하는 목적지는 목적지 후보 배열에 존재하는 목적지들을 의미하며, 이들을 전부 순회하여 다음 설명하는 방식대로 계산함으로써 각 목적지 후보들이 최단 경로를 만족하는지 확인할 수 있다.

그렇게 하면 g와 h를 거치는 방식은 총 두 가지가 존재하게 된다.

 

[s -> g -> h -> i] 또는 [s -> h -> g -> i]

 

따라서 각각 g와 h로 구간을 나누어 최단 경로를 구한 후 합한 것이 출발지 s에서 바로 목적지 i로 가는 최단 경로와 동일하다면, 해당 목적지 후보는 최단 경로가 되므로 목적지 후보에 적합한 것이다. 만약 최단 경로가 아닌 경우에는 목적지 후보가 되지 못한다.

좀 더 자세히 설명하자면, 다음과 같이 나타낼 수 있다.

 

(s에서 g까지의 최단 경로) + (g에서 h까지의 최단 경로) + (h에서 i까지의 최단 경로) == (s에서 i까지의 최단경로)

또는 

(s에서 h까지의 최단 경로) + (h에서 g까지의 최단 경로) + (g에서 i까지의 최단 경로) == (s에서 i까지의 최단경로)

 

위 두 가지 경우 중 하나라도 만족할 경우 해당 목적지 후보인 i는 목적지 후보에 적합한 것이므로 출력할 수 있다.

 

이 방식대로 문제를 풀면 다음과 같이 구현할 수 있다.

전체 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int T, n, m, t, s, g, h;
vector<int> ans, dis; // 목적지 후보, 각 인덱스까지의 최단거리
vector<pair<int, int>> graph[2001];

void dijkstra(int start) {
    dis[start] = 0; // 기준이 되는 출발지 거리 0
    priority_queue<pair<int, int>> pq;
    pq.push({0, start}); // 이동거리, 현재 위치

    while(!pq.empty()) {
        int curDis = -pq.top().first; // 이동거리 (음수화)
        int curPos = pq.top().second; // 현재 위치
        pq.pop();
        for (int i = 0; i < graph[curPos].size(); ++i) { // 인접한 정점의 개수만큼 순회
            int nDis = curDis + graph[curPos][i].first;
            int nPos = graph[curPos][i].second;
            // 현재 위치를 거쳐서 다음 위치로 가는 거리가 더 짧은 경우 최단 경로 갱신
            if (nDis < dis[nPos]) {
                dis[nPos] = nDis;
                pq.push({-nDis, nPos}); // 짧은 이동거리부터 우선순위 큐에 넣어지도록 음수화
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> T;
    for (int testCase = 0; testCase < T; ++testCase) {
        cin >> n >> m >> t >> s >> g >> h;
        // graph 초기화 (size() 함수 사용을 위한 graph 선언 및 초기화 방법)
        for (int i = 1; i <= n; i++) vector<pair<int, int>>().swap(graph[i]);
        ans = vector<int>(n + 1, 0);
        dis = vector<int>(n + 1, 1e9); // 최단 경로 비교를 위해 무한대로 초기화

        int first, second, thrid, thridPos; // 각 구간별 최단 경로 값, 3번째 위치

        for (int i = 0; i < m; ++i) {
            int a, b, d;
            cin >> a >> b >> d;
            // g, h 경로는 홀수화, 나머지 짝수화
            if ((a == g && b == h) || (a == h && b == g)) second = d; // 두 번째 구간 값
            // 양방향 도로
            graph[a].push_back({d, b});
            graph[b].push_back({d, a});
        }

        dijkstra(s);

        if (dis[g] < dis[h]) { // g가 h보다 가깝다면 
            first = dis[g]; // 첫 번째 구간 값
            thridPos = h; // 3번째 위치
        }
        else {
            first = dis[h]; // 첫 번째 구간 값
            thridPos = g; // 3번째 위치
        }

        for (int i = 0; i < t; ++i) {
            int x; cin >> x;
            ans[x] = dis[x]; // 출발점 s에서부터 목적지 후보 x까지의 최단 경로 값 전부 저장
        }

        dijkstra(thridPos); // 3번째 위치부터 시작하는 최단 경로 값

        for (int i = 1; i <= n; ++i) { // 홀수일 때만 출력 (오름차순)
            thrid = dis[i]; // 세 번째 구간 값
            if (ans[i] == first + second + thrid) cout << i << " ";
        }
        cout << "\n";
    }
    return 0;
}

---

2. g와 h의 거리만 홀수화하고, 나머지는 짝수화하여 목적지 후보가 홀수일 경우를 판단하기

이 경우는 정말 생각지도 못한 방법인 것 같았다.

일단 교차로 사이에는 도로가 많아봐야 1개인데, 입력받을 m개의 줄 중에서 g와 h 사이의 도로를 나타낸 것이 존재한다고 문제에서 정의했으므로 다음과 같이 나타낼 수 있다.

if ((a == g && b == h) || (a == h && b == g)) d = d * 2 - 1;
else d = d * 2;

입력받은 a, b, d 중에서 a, b가 g, h 또는 h, g인 경우, 홀수화를 해주고, 그 외에는 전부 짝수화를 해주면 된다.

이렇게 모든 도로에 2배씩 곱하여 홀수/짝수화를 하게 되면 값이 동등하게 곱해지기 때문에 결과에는 차질이 없다.

이 문제는 최단 경로 자체를 구하는 문제가 아니라, 최단 경로로 갈 수 있는 목적지 후보를 골라내는 것이기 때문에 이 방법이 가능한 것이다.

따라서 다익스트라 알고리즘을 통한 최단 경로 계산이 모두 끝난 후, 목적지 후보를 추출해낼 때 다음과 같은 조건문을 통해 판별할 수 있다.

if (d[i] % 2 == 1) cout << i << ' ';

 

즉, 출발지 s에서 목적지 후보 중 하나인 i까지 가는 경로의 길이가 홀수인 경우에만 출력이 되도록 하는 것이다. 이렇게 된다면, 목적지 후보로 가는 경로가 최단경로임을 뜻하는 바이다.

아래에는 해당 방식으로 푼 전체 코드이다.

전체 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int T, n, m, t, s, g, h;
vector<bool> candidates; // 목적지 후보
vector<int> dis; // 각 인덱스까지의 최단거리
vector<pair<int, int>> graph[2001];

void dijkstra(int start) {
    dis[start] = 0; // 기준이 되는 출발지 거리 0
    priority_queue<pair<int, int>> pq;
    pq.push({0, start}); // 이동거리, 현재 위치

    while(!pq.empty()) {
        int curDis = -pq.top().first; // 이동거리 (음수화)
        int curPos = pq.top().second; // 현재 위치
        pq.pop();
        for (int i = 0; i < graph[curPos].size(); ++i) { // 인접한 정점의 개수만큼 순회
            int nDis = curDis + graph[curPos][i].first;
            int nPos = graph[curPos][i].second;
            // 현재 위치를 거쳐서 다음 위치로 가는 거리가 더 짧은 경우 최단 경로 갱신
            if (nDis < dis[nPos]) {
                dis[nPos] = nDis;
                pq.push({-nDis, nPos}); // 짧은 이동거리부터 우선순위 큐에 넣어지도록 음수화
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> T;
    for (int testCase = 0; testCase < T; ++testCase) {
        cin >> n >> m >> t >> s >> g >> h;
        // graph 초기화 (size() 함수 사용을 위한 graph 선언 및 초기화 방법)
        for (int i = 1; i <= n; i++) vector<pair<int, int>>().swap(graph[i]);
        candidates = vector<bool>(n + 1, false);
        dis = vector<int>(n + 1, 1e9); // 최단 경로 비교를 위해 무한대로 초기화
        for (int i = 0; i < m; ++i) {
            int a, b, d;
            cin >> a >> b >> d;
            // g, h 경로는 홀수화, 나머지 짝수화
            if ((a == g && b == h) || (a == h && b == g)) d = d * 2 - 1;
            else d = d * 2;
            // 양방향 도로
            graph[a].push_back({d, b});
            graph[b].push_back({d, a});
        }
        for (int i = 0; i < t; ++i) {
            int x; cin >> x;
            candidates[x] = true;
        }

        dijkstra(s);

        for (int i = 1; i <= n; ++i) // 홀수일 때만 출력 (오름차순)
            if (candidates[i] && dis[i] % 2 == 1)
                cout << i << " ";
        cout << "\n";
    }
    return 0;
}

 

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

9370번: 미확인 도착지