백준 9370번 - 미확인 도착지

www.acmicpc.net/problem/9370

9370번: 미확인 도착지

다익스트라 알고리즘을 사용하여 해결할 수 있는 문제이다.

 

 

문제 분석

 

1. "목적지의 후보"들이 주어진다.

2. 목적지까지 반드시 "최단거리"로만 갈 것이다.

3. 반드시 "g와 h사이의 교차로"를 지나간다.

 

따라서 이 문제를 한 줄로 요약하면 다음과 같다.

 

"목적지의 후보들 중 g와 h 사이의 간선을 반드시 지나가는 경로가 최단 경로인 정점들을 모두 찾아라!"

 

 

 

해결 방법 

 

사실 문제를 보자마자 해결법이 떠올랐다.

 

왜냐하면 앞서서 포스팅했던 "특정한 최단 경로" 문제와 비슷한 유형이었기 때문이다.

 

목적지가 될 수 있다는 말은 시작점부터 g - h 간선을 거쳐서 목적지 후보에 도착했을 때, 해당 경로가 최단경로여야 한다.

 

여기서 함정이 있다.

 

문제에서 양방향 간선이라고 조건을 제시했으므로 g - h 간선이라는 말은 결국 g -> h, h -> g 이 두 가지 경우를 모두 의미한다.

 

즉, min( dis[start -> g -> h -> end] , dis[start -> h -> g -> end] )가  dis[start -> end] 보다 작거나 같아야 한다!

(이때 같아도 되는 이유는 start -> end 사이의 최단 경로가 g - h 간선을 거치는 경우일 수도 있기 때문!)

 

따라서 이제 우리가 구해야 할 것들은 다음과 같다.

 

1. 시작점부터 g까지의 최단 거리
2. 시작점부터 h까지의 최단 거리
3. g와 h사이의 간선의 가중치
4. g부터 도착점까지의 거리
5. h부터 도착점까지의 거리

1,2번은 다익스트라 한 번을 통해 구할 수 있다. 

 

3번은 간선의 가중치들을 입력받을 때 구해놓으면 된다.

 

4번과 5번은 각각 다익스트라 한 번을 통해 구할 수 있다.

 

뭐.. 다 구해놓기만 하면 정답을 구하는 건 어렵지 않다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;
 
vector<pair<int, int>>graph[2004];
bool check[2004];
int endp[104];  // 목적지 후보들
int stoa[2004]; // 시작점부터 도착점까지 직행 최단 거리를 저장하고 있는 배열
int gtoa[2004]; // g부터 다른 모든 점까지의 최단거리
int htoa[2004]; // h부터 다른 모든 점까지의 최단거리
 
void dijkstra(int s, int dis[]) {
    dis[s] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push(pii(0, s));
    while (!pq.empty()) {
        int now = pq.top().second;
        int wei = pq.top().first;
        pq.pop();
        if (check[now] == true) continue;
        check[now] = true;
        if (dis[now] < wei) continue;
        for (int i = 0; i < graph[now].size(); i++) {
            int next = graph[now][i].first;
            int w = graph[now][i].second;
            if (dis[now] + w < dis[next]) {
                dis[next] = dis[now] + w;
                pq.push(pii(dis[next], next));
            }
        }
    }
}
 
// 초기화 작업 꼭 해줘야 함!!!!!
void init() {
    // graph, check, stoa, gtoa, htoa
    memset(graph, 0, sizeof(graph));
    memset(check, false, sizeof(check));
    memset(stoa, 127, sizeof(stoa));
    memset(gtoa, 127, sizeof(gtoa));
    memset(htoa, 127, sizeof(htoa));
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t, n, m, k, s, g, h, a, b, d, x, gtoh;
    cin >> t;
    while (t--) {
        init();
        int INF = stoa[0];
        cin >> n >> m >> k;
        cin >> s >> g >> h;
        for (int i = 0; i < m; i++) {
            cin >> a >> b >> d;
            // 입력받을때 gtoh 미리 가지고 있기
            if ((a == g && b == h) || (a == h && b == g)) gtoh = d;
            // 양방향 간선임!
            graph[a].push_back(pii(b, d));
            graph[b].push_back(pii(a, d));
        }
        for (int i = 0; i < k; i++) {
            cin >> x;
            endp[i] = x;
        }
        dijkstra(s, stoa); // 시작점부터 다른 모든 지점까지의 최단거리 구하기
        memset(check, false, sizeof(check));
        dijkstra(g, gtoa); // g 부터 다른 모든 지점까지의 최단거리 구하기
        memset(check, false, sizeof(check));
        dijkstra(h, htoa); // h 부터 다른 모든 지점까지의 최단거리 구하기
        // 모든 도착지점들이 조건을 만족하는지 판단
        vector<int>ans;
        for (int i = 0; i < k; i++) {
            int node = endp[i];
            int temp;
            if (stoa[g] < stoa[h]) { // s-g가 s-h 보다 짧다면(최단)
                if (htoa[node] == INF) continue; // 경로가 존재하지 않는다면 불가!
                temp = stoa[g] + gtoh + htoa[node];
            }
            else {
                if (gtoa[node] == INF) continue;
                temp = stoa[h] + gtoh + gtoa[node];
            }
            if (temp <= stoa[node]) ans.push_back(node);
        }
        sort(ans.begin(), ans.end());
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i] << " ";
        }
        cout << "\n";
    }
}

 

이렇게 다익스트라 3번을 통해서 답을 구할 수 있었다.

조건을 만족시키는 경우를 찾아내는 게 문제의 핵심이었던 것 같다.

 

자꾸 헤더 파일을 include 하는 걸 까먹어서 컴파일 에러를 낸다..

이번 기회에 모든 헤더 파일을 include 해주는 bits를 찾아볼 생각이다..