백준 1504

ALGORITHM
2025-09-03

특정한 최단 경로

관련 개념

#다익스트라 #그래프 #골드

문제

백준 1504

📌 1 단계 : 문제 분석하기

  • 이 문제는 일단 다익스트라를 사용하라는 것이 너무나 자명하다. (최단 거리 + 그래프 문제)
  • 하지만, 특정 두 정점을 지나야한다는데에서 차이가 있다.
  • 이것도 너무 복잡하게 생각 할 필요 없다.
  • 특정 정점을 반드시 지나는 경로를 구하려면, 그 정점에서 다익스트라를 이용하면 된다.
  • 하나의 최단 경로를 찾는 것이 아니라, 여러 최단 경로를 이어 붙이는 문제

📌 2 단계 : 손으로 풀어보기

  • 두 정점 v1, v2에서 각각 다익스트라를 통해서 경로를 구한다
  • v1 + v2 를 더하고, (최단거리), 시작점 - v1 - v2 - 도착점과 시작점 - v2 - v1 - 도착점 중 더 짧은거리를 택하면 된다.

📌 3 단계 : 슈도 코드 작성하기

  • 생략

📌 4 단계 : 코드 작성하기

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
 
using namespace std;
typedef pair<int, int> pii;
 
const int INF = 1000000;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int V, E;
    cin >> V >> E;
    int ans = 0;
 
    vector<vector<pii>> graph(V + 1);
 
    for (int i = 0; i < E; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({ v, w });
        graph[v].push_back({ u , w });
    }
 
    int v1, v2;
 
    cin >> v1 >> v2;
 
    // 첫번 째 정점
    vector<int> distance(V + 1, INF);
    // 두번째 정점
    vector<int> distance2(V + 1, INF);
 
    // 최소 힙
    priority_queue<pii, vector<pii>, greater<pii>> pq;
 
    // 첫번째 노드 정보 초기화
    distance[v1] = 0;
    pq.push({ 0, v1 }); // {시작점까지의 거리(0), 시작 노드}
 
    while (!pq.empty()) {
        // 큐에서 가장 거리가 짧은 노드 정보를 꺼냄
        int dist = pq.top().first;
        int curr = pq.top().second;
        pq.pop();
 
        if (dist > distance[curr]) {
            continue;
        }
 
        for (auto& edge : graph[curr]) {
            int next = edge.first;
            int weight_to_next = edge.second;
 
            if (distance[next] > dist + weight_to_next) {
                distance[next] = dist + weight_to_next;
                pq.push({ distance[next], next });
            }
        }
    }
 
    // 두번째 노드 정보 초기화
    distance2[v2] = 0;
    pq.push({ 0, v2 }); // {시작점까지의 거리(0), 시작 노드}
 
    while (!pq.empty()) {
        int dist = pq.top().first;
        int curr = pq.top().second;
        pq.pop();
 
        if (dist > distance2[curr]) {
            continue;
        }
 
        for (auto& edge : graph[curr]) {
            int next = edge.first;
            int weight_to_next = edge.second;
 
            // 현재 노드를 거쳐 다음 노드로 가는 것이 더 짧을 경우
            if (distance2[next] > dist + weight_to_next) {
                // 거리 갱신 및 큐에 새로운 경로 추가
                distance2[next] = dist + weight_to_next;
                pq.push({ distance2[next], next });
            }
        }
    }
 
    // v1과 v2의 거리구하기
    ans += distance[v2];
 
    // v1이 S와 연결되는 경우와 N과 연결되는 경우 중 더 작은 값 찾기
    int final_distance = min((distance[1] + distance2[V]), (distance2[1] + distance[V]));
 
    ans += final_distance;
 
    if (ans >= INF) cout << -1;
    else cout << ans;
 
    return 0;
}

📌 5 단계 : 배운점

  1. 처음에는 INF 를 INT 상한선으로 잡았다가 오버플로우가 일어나서 실패했다.
  2. 두번째는 INF 를 너무 작은 값으로 잡았다 (간선의 수와 정점을 고려 X)
  3. ‘세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다.’ 라는 문장에 뇌정지가 왔다. 하지만 이 문장을 잘 생각해보자
    1. 집(1번)에서 출발해서 우체국(v1)에 들렀다가, 은행(v2)을 거쳐 회사(N)에 간다고 상상하자.
      • 집 → 우체국 최단 경로: 집 → 사거리 → 우체국
      • 우체국 → 은행 최단 경로: 우체국 → 사거리 → 은행
    2. 이 경우, 전체 이동 경로는 집 → 사거리 → 우체국 → 사거리 → 은행이 된다.
    3. 즉, 사거리를 두번 지나친다.
  4. 오타를 항상 확인하자!!!
  5. 머릿속이 너무 복잡해진다면, 그건 잘못 접근하고 있을 확률이 크다.