[Dijkstra]BOJ 9370_미확인 도착지

문제 링크 : www.acmicpc.net/problem/9370

9370번: 미확인 도착지

 

결국 문제는 특정한 하나의 간선을 출발지로부터의 최단경로에 포함하는 노드들을 구하는 것이다.

후술할 다른 풀이방법도 있지만, 문제의 의도에 따라 다익스트라 알고리즘을 적용해 정석으로 풀이해보자.

예제 그래프

위의 예제 그래프에서

2번 노드에서 어떤 목적지 후보 노드에 대한 최단경로가 1-3 간선을 포함하고 있다면,

1번 노드에서 그 목적지 후보 노드에 대한 최단거리는 출발 노드로부터 목적지 후보 노드까지의 최단경로 가중치에서

2번 노드에서 1번 노드까지의 최단 경로 가중치를 뺀 값이 된다.

 

쉽게 설명하자면, 2번 노드에서 6번 노드로 가는 최단경로는 2 - 1 - 3 - 6 에 가중치 합은 6이다.

2 - 1 - 3 - 6은 6번 노드에 대한 최단경로이므로, 이 경로에 포함된 다른 노드를 출발점으로 삼았을 때에도

그 최단경로는 위의 2 - 1 - 3 - 6 의 일부가 된다.

이를테면 1번 노드를 출발 노드로 생각했을 때, 6번 노드까지의 최단경로는 1 - 3 - 6이 될 것이고

3번 노드를 출발 노드로 생각한다면 최단경로는 3 - 6이 될 것이다.

 

출발지로부터 g까지의 최단경로 가중치 합(이하 A)과 출발지로부터 h까지의 최단경로 가중치 합(이하 B)을 구하고,

출발지로부터 목적지 후보까지의 최단경로 가중치 합을 C라 하자.  (여기까지 다익스트라 알고리즘이 1번 적용)

 

g를 출발점으로 한 목적지 후보까지의 거리를 A',   (다익스트라 알고리즘을 2번째 적용)

h를 출발점으로 한 목적지 후보까지의 거리를 B' 라 하면  (다익스트라 알고리즘을 3번째 적용)

C = A + A' = B + B' 임을 확인하면 된다.

 

예제에서는 2 ~ 1까지의 가중치가 1, 1 ~ 6까지의 가중치가 5,

2 ~ 3까지의 가중치가 4, 3 ~ 6까지의 가중치가 2므로,

2 ~ 6까지의 가중치 6 = 1 + 5 = 4 + 2이다. 따라서 6번 노드는 가능한 목적지 후보이다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>
 
#define INF 99999999
 
using namespace std;
typedef pair<int, int> p;
 
int n, m, t;
int s, g, h;
int dist[2001], targetdist[100][3];
vector<p> adj[2001];
vector<int> answer, target;
 
void dijkstra(int start) {
    fill(dist, dist + n + 1, INF);
    priority_queue<p> pque;
    dist[start] = 0;
    for (int i = 1; i <= n; i++) {
        if (i == start) pque.push({ 0, start });
        else pque.push({ -INF, i });
    }
 
    while (!pque.empty()) {
        p cur = pque.top();
        pque.pop();
 
        int distval = -cur.first;
        int node = cur.second;
 
        if (dist[node] >= distval) {
            for (int i = 0; i < adj[node].size(); i++) {
                p next = adj[node][i];
                if (dist[next.first] > distval + next.second) {
                    dist[next.first] = distval + next.second;
                    pque.push({ -dist[next.first], next.first });
                }
            }
        }
    }
}
 
void init() {
    int first, second, w;
    cin >> n >> m >> t;
    cin >> s >> g >> h;
 
    memset(targetdist, 0, sizeof(targetdist));
    for (int i = 1; i <= n; i++) adj[i].clear();
    target.clear();
 
    for (int i = 0; i < m; i++) {
        cin >> first >> second >> w;
        adj[first].push_back({ second, w });
        adj[second].push_back({ first, w });
    }
 
    for (int i = 0; i < t; i++) {
        cin >> first;
        target.push_back(first);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    int tc, far, close;
 
    cin >> tc;
    for (int i = 0; i < tc; i++) {
        init();
        answer.clear();
        //시작점 기준 다익스트라
        dijkstra(s);
 
        if (dist[g] > dist[h]) { far = g; close = h; }
        else { far = h; close = g; }
        for (int j = 0; j < target.size(); j++) 
            targetdist[j][0] = dist[target[j]];
        
        int dist_close = dist[close];
        int dist_far = dist[far];
        //close기준 다익스트라
        dijkstra(close);
        for (int j = 0; j < target.size(); j++)
            targetdist[j][1] = dist[target[j]];
 
        //far 기준 다익스트라
        dijkstra(far);
        for (int j = 0; j < target.size(); j++)
            targetdist[j][2] = dist[target[j]];
 
        for (int j = 0; j < target.size(); j++) {
            if (targetdist[j][0] == targetdist[j][1] + dist_close
                && targetdist[j][0] == targetdist[j][2] + dist_far)
                answer.push_back(target[j]);
        }
        
        sort(answer.begin(), answer.end());
        for (int j = 0; j < answer.size(); j++) {
            printf("%d", answer[j]);
            if (j < answer.size() - 1) printf(" ");
        }
        printf("\n");
    }
 
    return 0;
}

 

질문게시판에는 포함되어야 할 간선에만 가중치를 *2 +1 해주고,

나머지 간선에는 가중치를 * 2 해주는 방식을 사용한 풀이도 있었다.

 

즉, 포함되어야 할 간선의 가중치만 홀수로 만들어

한번의 다익스트라 적용을 통해 목적지 후보에 대한 최단거리 가중치 합이 홀수인지만 확인하면 되는 방식도 있었다.