BOJ 1504 - 특정한 최단 경로(C++)

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

문제를 푼 날짜: 2025. 06. 27

#graphs #shortest_path #dijkstra

내 풀이(C++)

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

using namespace std;
const int INF = 1000000000 / 3;

// N: 정점의 개수, E: 간선의 개수
int N, E;

// (to, weight)
vector<vector<pair<int, int>>> graph;

// Return: depart부터 arrival 까지 최단경로
int dijkstra(int depart, int arrival);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> E;
    graph.assign(N+1, vector<pair<int, int>>());

    for(int i = 0; i < E; i++){
        int src, dst, w;
        cin >> src >> dst >> w;
        graph[src].push_back({dst, w});
        graph[dst].push_back({src, w});
    }

    // 경유 지점
    int stop1, stop2;
    cin >> stop1 >> stop2;

    // 경우의 수는 1->stop1->stop2->N 또는 1->stop2->stop1->N
    int dist_two_stop = dijkstra(stop1, stop2);
    int ans = min(dijkstra(1, stop1) + dist_two_stop + dijkstra(stop2, N), dijkstra(1, stop2) + dist_two_stop + dijkstra(stop1, N));
    if(ans >= INF) cout << -1;
    else cout << ans;
    return 0;
}

int dijkstra(int depart, int arrival){
    vector<int> distance(N+1, INF);
    // (거리, 노드번호)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    distance[depart] = 0;
    pq.push({0, depart});

    while(!pq.empty()){
        auto [cost, now] = pq.top();
        pq.pop();

        // 이미 더 짧은 경로 존재하면 skip
        if(distance[now] < cost) continue;

        for(auto [next, weight] : graph[now]){
            int new_cost = cost + weight;
            if(new_cost < distance[next]){
                distance[next] = new_cost;
                pq.push({new_cost, next});
            }
        }
    }
    return distance[arrival];
}

---

🔎 문제 설명

• 정점 1번에서 N번까지 가는데, 주어진 두 정점(stop1, stop2)을 반드시 경유해야 한다.
• 경로 순서는 다음 두 가지가 가능:
  • $1 \rightarrow \text{stop1} \rightarrow \text{stop2} \rightarrow N$
  • $1 \rightarrow \text{stop2} \rightarrow \text{stop1} \rightarrow N$
• 이 두 경우 중 최단 경로의 길이를 구하라.

---

⛔ 내가 틀렸던 부분

1. INF 값 오버플로우 주의

• 처음엔 INF = 10^9로 설정했는데,
• 최단거리끼리 3번 덧셈을 하면 $10^9 \times 3 = 3 \times 10^9$ 이 되어 int 오버플로우가 발생할 수 있었다.
• → 수정 : INF = 10^9 / 3 로 설정해서 여러 번 더해도 안전하도록 했다.

2. 무방향 간선 입력 실수

• 입력을 받을 때 아래처럼 한 방향만 추가했음:

  graph[src].push_back({dst, w});

• 그러나 무방향이므로 반드시 반대 방향도 추가해야 한다:

  graph[dst].push_back({src, w});

3. dijkstra 호출 최적화

• 내 풀이는 다익스트라를 5번 호출했음:
  • dijkstra(1, stop1)
  • dijkstra(stop1, stop2)
  • dijkstra(stop2, N)
  • dijkstra(1, stop2)
  • dijkstra(stop1, N)
• 그러나 아래처럼 하면 3번만 호출해도 모든 정보를 얻을 수 있다:
  • 다익스트라(1) → stop1, stop2, N까지 거리 얻음
  • 다익스트라(stop1) → stop2, N까지 거리 얻음
  • 다익스트라(stop2) → N까지 거리 얻음

이 문제에서는 시간 제한이 엄청 빡빡하지는 않아 다익스트라 5번 호출을 해도 문제가 없었으나, 더 타이트한 조건이라면 위와 같이 최적화할 수 있다.