[ 백준 9370 ] 미확인 도착지 (C++)

백준의 미확인 도착지(9370) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

이 문제는, 주어진 시작점 s에서 'g - h' 혹은 'h - g' 를 거쳐서 가는 루트가 최단거리가 되는 정점을 주어진 후보 중에서

찾으면 되는 문제이다.

양의 가중치만 존재하는 그래프에서 최단경로를 찾아야 하는 문제이기 때문에 본인은 다익스트라 알고리즘을 이용해서

접근해 보았다.

[ 다익스트라 알고리즘 알아보기(Click) ]

본인은 총 3번의 다익스트라 알고리즘을 사용했다.그리고, 3번의 다익스트라에서 구한 최단경로들을 저장할 3개의 int 형

1차원 배열을 선언해서 최단경로들을 저장해 주었다.

우리가 3번의 다익스트라를 통해서 구하고자 하는 것은 다음에 해당하는 정점이다.

S → G → H → ? 가 최단경로가 되는 정점.

S → H → G → ? 가 최단경로가 되는 정점.

위에서 말한 2가지 경우에서 '?' 에 해당하는 정점을 찾고자 하는 것이다.

첫 번째 다익스트라 알고리즘은 "시작점에서 G 와 H 점 까지의 거리를 구하기 위해" 서 사용해주었다.

따라서 첫 시작 점을 S로 두고 탐색을 시작했으며, 이 때 구한 최단경로들을 S[] 라는 배열에 저장했다고 생각하자.

S[a] = b 의 의미는 "시작점에서 a정점으로 가는데 걸리는 최단 경로는 b입니다." 이다.

두 번째 다익스트라 알고리즘은 "정점 G에서 다른 정점들 까지의 거리를 구하기 위해" 서 사용해 주었다.

시작점을 'G로 두고 탐색을 시작했으며, 이 때 구한 최단경로를 G[] 라는 배열에 저장했다고 생각하자.

G[a] = b 의 의미는 "정점 G에서 a정점으로 가는데 걸리는 최단 경로는 b 입니다." 이다.

세 번째 다익스트라 알고리즘은 "정점 H에서 다른 정점들 까지의 거리를 구하기 위해" 서 사용해 주었다.

시작점을 'H'로 두고 탐색을 시작했으며, 이 떄 구한 다른 정점들 까지의 최단경로를 H[] 라는 배열에 저장했다고

생각하자.
H[a] = b 의 의미는 "정점 H에서 a정점으로 가는데 걸리는 최단 경로는 b 입니다." 이다.

그럼 이제 모든 최단경로를 다 구했으니, 문제의 입력에서 주어진 후보군들 중에서 정답이 될만한 후보들을 찾아주기만

하면 된다.

정답이 될만하다 라는 것은 다음과 같은 조건을 만족해야 한다.

예를 들어서 'A' 라는 정점이 후보일 때,

"시작점에서 A로 가는데 걸리는 최단경로가, 시작점 → G → H → A 로 가는 경로와 동일하거나,

 시작점 → H → G → A 로 가는 경로와 동일" 해야 한다. 

그래야지만, 'A'라는 정점으로 가기 위한 최단경로의 루트에는 'G - H' 혹은 'H - G'가 포함될 것이고, 이는 정답의 조건에

만족하게 된다.

위에서 구한 배열을 이용해서 표현하자면 다음 처럼 구현할 수 있다.

S[A] == S[G] + G[H] + H[A] or S[A] == S[H] + H[G] + G[A] 이렇게 성립하는지 확인을 해주면 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
#define endl "\n"
#define MAX 2010
#define INF 987654321
using namespace std;
 
int N, M, T, S, G, H, Dist_GH;
int Dist_S[MAX];
int Dist_G[MAX];
int Dist_H[MAX];
 
vector<pair<int,int>> V[MAX];
vector<int> Candidate;
 
void Initialize()
{
    for (int i = 0; i < MAX; i++)
    {
        V[i].clear();
        Dist_S[i] = INF;
        Dist_G[i] = INF;
        Dist_H[i] = INF;
    }
    Candidate.clear();
}
 
void Input()
{
    cin >> N >> M >> T;
    cin >> S >> G >> H;
    for (int i = 0; i < M; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        V[a].push_back(make_pair(b, c));
        V[b].push_back(make_pair(a, c));
    }
    for (int i = 0; i < T; i++)
    {
        int a; cin >> a;
        Candidate.push_back(a);
    }
}
 
void Dijkstra(int Start, int A[MAX])
{
    priority_queue<pair<int, int>> PQ;
    PQ.push(make_pair(0, Start));
    A[Start] = 0;
 
    while (PQ.empty() == 0)
    {
        int Cost = -PQ.top().first;
        int Cur = PQ.top().second;
        PQ.pop();
 
        for (int i = 0; i < V[Cur].size(); i++)
        {
            int Next = V[Cur][i].first;
            int nCost = V[Cur][i].second;
 
            if (A[Next] > Cost + nCost)
            {
                A[Next] = Cost + nCost;
                PQ.push(make_pair(-A[Next], Next));
            }
        }
    }
}
 
void Solution()
{
    Dijkstra(S, Dist_S);
    Dijkstra(G, Dist_G);
    Dist_GH = Dist_G[H];
    Dijkstra(H, Dist_H);
    sort(Candidate.begin(), Candidate.end());
    for (int i = 0; i < Candidate.size(); i++)
    {
        int Dest = Candidate[i];
        if (Dist_S[Dest] == Dist_S[G] + Dist_GH + Dist_H[Dest]) cout << Dest << " ";
        else if (Dist_S[Dest] == Dist_S[H] + Dist_GH + Dist_G[Dest]) cout << Dest << " ";
    }
    cout << endl;    
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}