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

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

 

 

알고리즘 종류

    - 최단거리

    - 다익스트라

 

 

 

사고 과정

    - 출발 정점 1과 도착 정점 n은 정해져 있다. 그리고 이 사이에 v1과 v2라는 특정된 정점이 있다. 특정된 정점을 지나간다는 것은 특정 정점이 도착 정점이 된다는 것을 의미한다. 경우를 나열해 보면, 1->v1->v2->n 또는 1->v2->v1->n이다. 경우 1을 가지고 설명해보면, 1에서 v1로 가는 최단거리에 다익스트라 알고리즘 적용, v1에서 v2로 가는 최단거리에 다익스트라 알고리즘 적용, v2에서 n으로 가는 최단거리에 다익스트라 적용을 하면된다.

        1. 경우를 2개로 나눈다. 1->v1->v2->n 그리고 1->v2->v1->n

        2. 각 경우 마다 다익스트라 알고리즘으로 최단거리를 구한다.

        3. 두 경우 모두 최단 거리를 구할 수 없는 경우, 즉, 거리가 INF 이상인 경우에는 -1를 출력한다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int n, e;
int v1, v2;
int answer;
int dist[801];
int INF = 98765432;
 
vector<vector<pair<int, int> > > edges;
 
 
void dijkstra(int v){
    fill(&dist[0], &dist[n+1], INF);
    dist[v] = 0;
    priority_queue<pair<int, int> > pq;
    pq.push({v, 0});
    
    while(!pq.empty()){
        int cur_node = pq.top().first;
        int cur_dist = -pq.top().second;
        pq.pop();
        
        if(dist[cur_node] < cur_dist) continue;
        
        for(int i=0; i<edges[cur_node].size(); i++){
            int next_node = edges[cur_node][i].first;
            int next_dist = cur_dist + edges[cur_node][i].second;
            
            if(dist[next_node] > next_dist){
                dist[next_node] = next_dist;
                pq.push({next_node, -next_dist});
            }
        }
    }
}
 
 
void solution(){
    
    int path1, path2;
    
    // 2개의 경우에 최단거리 계산  
    dijkstra(1);
    path1 = dist[v1];
    path2 = dist[v2];
    
    dijkstra(v1);
    path1 += dist[v2];
    path2 += dist[n];
    
    dijkstra(v2);
    path1 += dist[n];
    path2 += dist[v1];
    
    // 두 개 모두 INF 이상이 나오면 중간에 이어지는 경로가 없다는 의미 
    answer = min(path1, path2);
    if(answer >= INF) answer = -1;
    
    cout << answer << endl;
}
 
 
int main(void){
    
    cin >> n >> e;
    
    edges.resize(n+1);
    
    int a, b, c;
    for(int i=0; i<e; i++){
        // 양방향 그래프  
        cin >> a >> b >> c;
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
        
    }
    cin >> v1 >> v2;
    
    solution();
}

 

 

 

시행착오

    - 경우가 2개라고 생각하지 못했다. 그래서 정점 4개(1, v1, v2, n)을 출발 정점으로 해서 모든 정점에 가는 최단 거리를 구했다. 그러면 완전 그래프를 만들 수 있다. 그리고 MST를 활용하여 모든 정점을 최소 비용으로 연결하는 그래프를 구했다. 나는 이 최소 비용 트리의 구성이 시작은 1 정점이고 마지막이 n 정점이라고 생각했다. 그러나 항상 그렇지만 않았다. v2 - 1 - v1 - n 경우가 최소 비용 트리일 수 있기 때문이다. 몇 분을 분석하고 고민해서 2개의 경로로 나눌 수 있다는 것을 알게 되었다.