[BOJ] #1504 특정한 최단 경로

https://www.acmicpc.net/problem/1504

---

문제에서 요구하는 조건은 상당히 간단하다. 특정 정점 두개를 입력받아서 해당 정점들을 무조건 통과하는 경로 중 최단 경로를 출력하면 된다. 이때 출발지점은 1로 고정이고, 도착지점은 N으로 고정이다. 즉, 출발지점 -> v1 -> v2 -> 도착지점 이렇게 3개의 경로로 나누어 다익스트라를 3번 수행해주면 된다.

이때 주의할 점은 v1 -> v2 로 가는 경우와 v2 -> v1으로 가는 경우가 다르기 때문에 케이스를 두개로 잡고 계산하여야 한다. 기존에 void 타입으로 쓰던 dijkstra algorithm을 int 타입 벡터 dist를 리턴하도록 설계하여 각 경로마다 다른 dist 벡터를 도출하고, 도출된 dist 벡터에서 각 출발지와 도착지를 적절하게 세팅하여 최종 출력값을 이끌어 내면 된다.

처음에 접근할때는 dijkstra 함수 내부에서 v1이나 v2 정점을 방문할때 따로 로직 처리가 들어가는줄 알았다가 경로 자체를 분할하여 다익스트라를 3번 수행하는 방향으로 바꾸어 풀었다. 특정 정점을 무조건 지나도록 해야할때 흔히 쓰는 방식인 듯 하여 익혀두면 좋을 것 같다.

 

이전에 정점분할 테크닉 문제를 풀어본 기억이 있어 이 문제도 그런건가 했는데, 정점 분할 기법은 그래프에서 특정 정점을 두 개의 정점으로 분리하여, 한 정점을 최대 한 번만 지나도록 특정 제약을 적용할 때 사용한다고 한다. 딱히 정점 분할 문제는 아닌 것 같고, 그저 다익스트라를 3번 수행하면 쉽게 풀 수 있는 문제였다.

아 그리고 마지막에 95% 쯤에서 틀렸습니다가 떴는데 간선의 갯수가 0인 그래프를 반례로 고려하지 않아서 그런 듯 했다. 마지막 출력시에 total1이나 total2가 0보다 작거나 같은 경우를 모두 걸러주니 바로 정답 처리가 되었다.

---

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define MAX 805
#define INF 987654321

using namespace std;

int V,E, v1,v2;
vector<pair<int,int>> Graph[MAX];

// 다익스트라 알고리즘 함수
vector<int> dijkstra(int start) {
    vector<int> dist(V+1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int currentDist = pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();

        if (currentDist > dist[currentNode]) continue;

        for (auto& edge : Graph[currentNode]) {
            int nextNode = edge.first;
            int weight = edge.second;

            if (dist[currentNode] + weight < dist[nextNode]) {
                dist[nextNode] = dist[currentNode] + weight;
                pq.push({dist[nextNode], nextNode});
            }
        }
    }

    return dist;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    cin >> V >> E;

    for (int i=0; i<E; i++) {
        int a,b,c;
        cin >> a >> b >> c;

        Graph[a].push_back(make_pair(b,c));
        Graph[b].push_back(make_pair(a,c));
    }
    cin >> v1 >> v2;

    vector<int> costA = dijkstra(1);
    vector<int> costv1 = dijkstra(v1);
    vector<int> costv2 = dijkstra(v2);

    int total1 = costA[v1] + costv1[v2] + costv2[V];
    int total2 = costA[v2] + costv2[v1] + costv1[V];

    if ((total1 >= INF && total2 >= INF) || total1 <= 0 || total2 <= 0) cout << -1 << '\n';
    else cout << min(total1, total2) << '\n';

    return 0;
}