[ 백준 1504 ] 특정한 최단 경로 (C++)

백준의 특정한 최단 경로(1504) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1번 정점에서 N번 정점으로 최단 거리로 이동하려고 하는데, 반드시 거쳐야 하는 2개의 정점을 거쳐서 갈 때의 최단 거리를

구해야 하는 문제이다.

본인은 다익스트라 알고리즘을 이용해서 접근해 보았다.

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

그럼, 지금부터 '반드시 거쳐야 하는 2개의 정점을 A, B' 라고 표현하겠다.

즉, 1번정점에서 출발해서 A와 B를 모두 거친 후에, N번 정점으로 가는데 걸리는 최단경로를 구해보자.

위에서 말한 최단 경로를 구할 수 있는 2가지 방법이 있다.

1 → A → B → N 으로 가는 방법이 있고, (1번방법)

1 → B → A → N 으로 가는 방법이 있다. (2번방법)

문제에서 원하는 답은 '최단 거리' 이기 때문에, 위에서 말한 2가지 방법 중 더 짧은 경로로 갈 수 있는 방법을

정답으로 출력시켜주면 된다.

본인은 구현할 때 다익스트라 알고리즘을 총 4번 진행해 주었다.

첫 번째 다익스트라

- 1번 정점에서 A정점과, B정점으로 가는데 걸리는 최단 경로를 알아내기 위한 다익스트라 탐색.

두 번째 다익스트라

- A번 정점에서 B정점으로 가는데 걸리는 최단 경로를 알아내기 위한 다익스트라 탐색.

  시작점을 'A'로 삼아서 다익스트라를 진행해 주었지만, 결국 이 다익스트라를 통해서 A → B 의 거리를 알았다면,

  B → A 거리 또한 알아낸 셈이다. 왜냐하면, 방향이 없는 그래프이기 때문에 A정점에서 B정점으로 가는데 걸리는

  최단경로나, B정점에서 A정점으로 가는데 걸리는 최단경로가 같을 것이기 때문이다.

세 번째 다익스트라

- A정점에서 N번 정점으로 가는데 걸리는 최단 경로를 알아내기 위한 다익스트라 탐색.

네 번째 다익스트라

- B정점에서 N번 정점으로 가는데 걸리는 최단 경로를 알아내기 위한 다익스트라 탐색.

위와 같이, 총 4번의 다익스트라를 진행하면서, 걸리는 최단경로를 모두 더해주었다.

물론, 1번 방법, 2번 방법 따로 따로 더해주었다. 그리고 최단경로가 존재하지 않을 시, -1 을 출력하라고 했는데,

이를 위해서 1번 방법과 2번 방법에 대한 Flag를 하나 만들어서 '현재 이 방법으로 N번 정점에 갈 수 있는지' 를

판단해 주었다.

최종적으로, 1번 방법에 대한 Flag, 2번 방법에 대한 Flag 모두 'false' 라면 N번 정점까지 갈 수 없음을 의미하기 때문에

-1 을 출력해 주는 식으로 구현하였다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 810
#define INF 987654321
using namespace std;
 
int N, E, A, B, Answer;
int Dist[MAX];
vector<pair<int, int>> V[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N >> E;
    for (int i = 0; i < E; 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));
    }
    cin >> A >> B;
}
 
void Dijkstra(int Start)
{
    priority_queue<pair<int, int>> PQ;
    Dist[Start] = 0;
    PQ.push(make_pair(0, Start));
 
    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 (Dist[Next] > Cost + nCost)
            {
                Dist[Next] = Cost + nCost;
                PQ.push(make_pair(-Dist[Next], Next));
            }
        }
    }
}
 
void Solution()
{
    bool Flag1, Flag2;
    Flag1 = Flag2 = true;
 
    for (int i = 1; i <= N; i++) Dist[i] = INF;
    Dijkstra(1);
    int Route1 = Dist[A];
    int Route2 = Dist[B];
    if (Route1 == INF) Flag1 = false;
    if (Route2 == INF) Flag2 = false;
 
    for (int i = 1; i <= N; i++) Dist[i] = INF;
    Dijkstra(A);
    if (Flag1 == true) Route1 = Route1 + Dist[B];
    if (Flag2 == true) Route2 = Route2 + Dist[B];
 
    for (int i = 1; i <= N; i++) Dist[i] = INF;
    Dijkstra(B);
    if (Flag1 == true) Route1 = Route1 + Dist[N];
 
    for (int i = 1; i <= N; i++) Dist[i] = INF;
    Dijkstra(A);
    if (Flag2 == true) Route2 = Route2 + Dist[N];
 
    if (Flag1 == false && Flag2 == false) Answer = -1;
    else
    {
        Answer = Min(Route1, Route2);
    }
 
    if (Answer == INF) Answer = -1;
}
 
void Solve()
{
    Input();
    Solution();
 
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}
 
 

cs