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

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/1504

---

2. 풀이 과정

• 문제 해결의 흐름

1.  제목, 입력값, 요구사항을 파악해보면 최단 경로 문제, 그중에서도 가중치 그래프에서 특정 시작점으로부터 다른 모든 정점들까지의 최단 경로를 구하는 '다익스트라 알고리즘'을 활용하는 문제 유형임을 쉽게 파악 가능합니다.
2.  따라서 이 문제는 다익스트라 알고리즘을 사용하며 다음 2가지 조건을 만족시키는 경우의 최단 경로를 구해야 합니다. 
   • 조건 1 : 1~N까지 이동할 때 반드시 두 정점 v1, v2를 거쳐야 한다.
   • 조건 2 : 한 번 이동하였던 정점과 간선은 다시 이동할 수 있다.
3. 위 2가지 조건을 만족하는 최단 거리는 다음 2가지 경우뿐이라고 생각되었습니다.
   • 경우 1 : 1 -> v1 -> v2 -> N
   • 경우 2 : 1 -> v2 -> v1 -> N
4. 따라서 다음 5가지 거리만을 구하면, 쉽게 문제 조건을 만족하는 최단 경로의 길이를 구할 수 있을 거 같다는 생각이 들었습니다!
   • 1 -> v1
   • 1 -> v2
   • v1 -> v2 (v2 -> v1이기도 함)
   • v1 -> v2 
   • v1 -> N
   • v2 -> N
5.  다익스트라 알고리즘을 처음 적용해보았기에 구현함에 있어 어색함이 있었지만, 알고리즘 자체를 이해하고 나니 문제의 조건은 단순하였습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

// 무한대 설정
const long long INF = numeric_limits<long long>::max();

// 다익스트라 알고리즘 : 가중치 그래프에서 특정 '시작점'으로부터 다른 '모든 정점'까지의 '최단 경로'를 구하는 알고리즘
void dijkstra(int start, const vector<vector<pair<int, int> > >& graph, vector<long long>& dist) {
    // 최소 힙 구조의 우선순위 큐 (거리, 노드)
    priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<pair<long long, int> > > pq;

    // 시작 노드 초기화!
    dist[start] = 0; // 시작 노드에서 자신으로의 거리는 0임
    pq.push(make_pair(0, start));

    // 핵심 로직 ⭐️
    while(!pq.empty()) {
        long long cur_dist = pq.top().first; // 현재 노드까지의 거리
        int cur_node = pq.top().second; // 현재 노드
        pq.pop();

        // 현재 노드가 이미 처리되었다면 무시함 (다익스트라 알고리즘은 항상 최단 거리를 우선적으로 계산하니깐)
        if (cur_dist > dist[cur_node]) continue;

        // 모든 인접 노드 탐색하여 최소 거리 비용 찾기 ⭐️
        for (pair<int, int> neighbor : graph[cur_node]) {
            int next_node = neighbor.first; // 인접 노드
            int weight = neighbor.second; // 가중치

            long long cost = dist[cur_node] + weight; // 현재 노드에서 인접 노드까지의 거리 비용
            if (cost < dist[next_node]) {
                dist[next_node] = cost;
                pq.push(make_pair(cost, next_node));
            }
        }
    }
}

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

    // 0. 입력 받기
    int N, E; // 정점의 개수, 간선의 개수 (2 <= N <= 800, 0 <= E <= 20만)
    cin >> N >> E;
    vector<vector<pair<int, int> > > graph(N + 1); // 양방향 그래프
    for (int i = 0; i < E; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c)); // a~b 거리 : c
        graph[b].push_back(make_pair(a, c)); // b~a 거리 : c
    }
    int v1, v2; // 반드시 거쳐가야하는 정점 2개
    cin >> v1 >> v2;

    // 1. 최단 거리 구하기
    // [조건 1] 1~N까지 이동할 때 반드시 두 정점 v1, v2를 거쳐야함
    // [조건 2] 한번 이동했던 정점과 간선를 다시 이동할 수 있음
    vector<long long> dist1(N + 1, INF); // 거리 배열 초기화
    dijkstra(1, graph, dist1);
    long long d1 = dist1[v1]; // 1 -> v1 거리
    long long d2 = dist1[v2]; // 1 -> v2 거리

    vector<long long> dist_v1(N + 1, INF);
    dijkstra(v1, graph, dist_v1);
    long long v1_to_v2 = dist_v1[v2]; // v1 -> v2 거리 (v2 -> v1이기도 함)
    long long v1_to_N = dist_v1[N];   // v1 -> N 거리

    vector<long long> dist_v2(N + 1, INF);
    dijkstra(v2, graph, dist_v2);
    long long v2_to_N = dist_v2[N];   // v2 -> N 거리

    // 2. 두 가지 경우의 경로 계산하기
    // 경로 (1) 1 -> v1 -> v2 -> N
    long long path1;
    if (d1 != INF && v1_to_v2 != INF && v2_to_N != INF) { // INF와 같은 경우는 서로 연결 안된, 즉 도달할 수 없는 경우임
        path1 = d1 + v1_to_v2 + v2_to_N;
    } else {
        path1 = INF;
    }

    // 경로 (2) 1 -> v2 -> v1 -> N
    long long path2;
    if (d2 != INF && v1_to_v2 != INF && v1_to_N != INF) {
        path2 = d2 + v1_to_v2 + v1_to_N;
    } else {
        path2 = INF;
    }

    // 3. 출력하기
    long long result = min(path1, path2);
    if (result == INF) {
        cout << -1 << "\n";
    } else {
        cout << result << "\n";
    }

    return 0;
}

---

3. 후기

 다익스트라 알고리즘을 구현하며 최단 경로 문제를 푸는 방법을 깨달은 거 같아 뿌듯합니다!