백준_1504_특정한 최단 경로[C++]

[문제링크]

다익스트라

다익스트라를 사용하면 된다. 처음에는 일반적인 bfs를 사용했는데 안풀렸다. 찾아보니까 weighted Edge를 가진 그래프 문제에서는 bfs를 사용하면 최적 해를 보장할 수 없다는 것이 생각났다. 아… 자료구조 시간에 배웠던 기억이 난다. Lessssgo

---

접근

반드시 거쳐야하는 하는 정점의 id는 A와B라고 가정하고 최종 목표 id는 C라고 가정해보자. 그러면 2가지 path가 존재한다.

path1 = 1->A->B->C path2 = 1->B->A->C

그러나 무지성으로 다음과 같이 dijkstra를 사용하면 안된다. 처음 나의 풀이였다 😢

---

잘못된 접근

//int dijkstra(u,v) => 정점 u에서 v까지의 최단 거리를 반환해주는 함수
... 
int path1 = dijkstra(1,A) + dijkstra(A,B) + dijkstra(B,C);
int path2 = dijkstra(1,B) + dijkstra(B,A) + dijkstra(A,C);
int ans = min(path1,path2);
...

이렇게 구현하면 계속 wrong answer가 발생할 것이다. 예를 들어, dijkstra(1,A) =3, dijkstra(A,B) = 도달불가(INF), dijstra(B,C) = 2라면 의도하고자 하는 답을 찾을 수 없다. 그렇다. 모든 sub-path들의 값을 확인해줘야한다.

---

옳바른 접근

    int a1 = dijkstra(1, v1);
    int a2 = dijkstra(v1, v2);
    int a3 = dijkstra(v2, N);

    int b1 = dijkstra(1, v2);
    int b2 = dijkstra(v2, v1);
    int b3 = dijkstra(v1, N);

    int path1 = (a1 >= INF) || (a2 >= INF) || (a3 >= INF) ? INF : a1 + a2 + a3;
    int path2 = (b1 >= INF) || (b2 >= INF) || (b3 >= INF) ? INF : b1 + b2 + b3;

    int ans = min(path1, path2);
    if (ans == INF) cout << -1 << "\n";
    else cout << ans << "\n";

sub-path들의 값이 하나라도 도달불가라면, 그 경로를 INF값으로 세팅하여 unreachable path로 체크한다.

Full code

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>

#define MAXSIZE 801
using namespace std;
int N, E;
vector<vector<pair<int, int>>> adj(MAXSIZE);

const int INF = 1e9;

void insertEdge(int v1, int v2, int w) {
    adj[v1].push_back({v2, w});
    adj[v2].push_back({v1, w});
    return;
}

int dijkstra(int v1, int v2) {
    int dict[N + 1];
    for (int i = 1; i <= N; i++) dict[i] = INF;
    dict[v1] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push({0, v1});
    while (!pq.empty()) {
        int cur_cost = -pq.top().first;
        int cur_vid = pq.top().second;
        pq.pop();
        for (auto vid_weight: adj[cur_vid]) {
            int next_vid = vid_weight.first;
            int next_cost = cur_cost + vid_weight.second;
            if (dict[next_vid] > next_cost) {
                dict[next_vid] = next_cost;
                pq.push({-next_cost, next_vid});;
            }
        }
    }
    return dict[v2];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> E;
    while (E--) {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;
        insertEdge(v1, v2, w);
    }

    int v1, v2;
    cin >> v1 >> v2;

    int a1 = dijkstra(1, v1);
    int a2 = dijkstra(v1, v2);
    int a3 = dijkstra(v2, N);

    int b1 = dijkstra(1, v2);
    int b2 = dijkstra(v2, v1);
    int b3 = dijkstra(v1, N);

    int path1 = (a1 >= INF) || (a2 >= INF) || (a3 >= INF) ? INF : a1 + a2 + a3;
    int path2 = (b1 >= INF) || (b2 >= INF) || (b3 >= INF) ? INF : b1 + b2 + b3;

    int ans = min(path1, path2);
    if (ans == INF) cout << -1 << "\n";
    else cout << ans << "\n";

    return 0;
}