백준 No.1504 [특정한 최단 경로]

Baekjoon Online Judge No.1504 [특정한 최단 경로]

---

 Problem

1504번: 특정한 최단 경로

---

   Code   

#include <iostream>
#include <vector>
#include <queue>
#define dist first
#define vertex second
 
using namespace std;
typedef pair<int, int> PII;
 
const int INF = 2100000000;
int V, E;
vector<vector<PII>> node;
 
int solve(int vertex_start, int vertex_target) {
    vector<int> dist_to(V + 1, -1); // dist_to[i] == distance between vertex_start and i
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    // first = dist, second = vertex : defined at line #4, #5
 
    dist_to[vertex_start] = 0;
    pq.push(PII(dist_to[vertex_start], vertex_start));
 
    while (!pq.empty()) {
        int curVer = pq.top().vertex;
        int curCost = pq.top().dist;
 
        pq.pop();
 
        if (curCost > dist_to[curVer]) continue;
 
        for (int i = 0; i < node[curVer].size(); i++) {
            int nextVer = node[curVer][i].vertex;
            int nextCost = curCost + node[curVer][i].dist;
 
            if (dist_to[nextVer] == -1 || dist_to[nextVer] > nextCost) {
                dist_to[nextVer] = nextCost;
                pq.push(PII(nextCost, nextVer));
            }
        }
    }
 
    return dist_to[vertex_target];
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> V >> E;
 
    node.resize(V + 1);
 
    for (int i = 0; i < E; i++) {
        int s, e, v;
        cin >> s >> e >> v;
 
        node[s].push_back(PII(v, e));
        node[e].push_back(PII(v, s));
    }
 
    int visit1, visit2;
    cin >> visit1 >> visit2;
 
    int s_to_v1 = solve(1, visit1);
    int s_to_v2 = solve(1, visit2);
 
    int between_v = solve(visit1, visit2);
 
    int v1_to_e = solve(visit2, V);
    int v2_to_e = solve(visit1, V);
    
    if (s_to_v1 != -1 && s_to_v2 != -1 && between_v != -1 && v1_to_e != -1 && v2_to_e != -1)
        cout << between_v + min(s_to_v1 + v1_to_e, s_to_v2 + v2_to_e);
    else cout << -1;
}

---

   How to solve   

  제일 일반적인 Dijkstra문제(2021/02/08 - [C++ Algorithm/Dijkstra] - Dijkstra (다익스트라))에서 살짝 변형을 하면 풀 수 있었다.

 

• 양방향 간선이므로 #58처럼 e 정점에서 v 정점으로 가는 node도 추가를 해 주었다.

양방향 간선

  첫 번째 경유지를 visit1, 두 번째 경유지를 visit2라고 할 때 두 가지 경우가 나온다.

 

• Start vertex (s) ----------> visit1 ----------> visit2 ----------> End vertex (e)
• Start vertex (s) ----------> visit2 ----------> visit1 ----------> End vertex (e)

이 두 경우중 더 작은 거리를 가지는 경우가 정답이 된다.

  기본적인 Dijkstra 에선 시작 정점에 대한 정보로 모든 정점들에 대한 최소 거리를 구했는데 Dijkstra를 구하는 함수에 (#14 line) 시작정점과 끝정점에 대한 정보를 주고, 입력된 시작정점부터 끝정점까지 가는 최소 거리를 return하도록 했다.

 

  위 코드에선 요구한 data들의 범위나 개수가 그렇게 많지 않아서 Dijkstra를 구하는 solve(...)를 그때그때 선언하여 했지만 Memoization을 해놓고 사용해도 좋을 것 같다. 만약 이 방법을 사용한다면, 시작점으로 주어질 경우들에 대해서만 미리 MEmoization을 해놓으면 될 것이다.

 

  만약 #64 ~ #70 의 변수들 중 단 하나라도 '-1'의 값을 가지는 변수가 있다면, 이 말은 즉슨 가고자 하는 어느 두 정점 사이 가는 방법이 없다는 말 이므로 '-1'을 출력했다.

 

  BFS에서도 단방향, 양방향에 대한 개념을 알 수 있지만 이 문제에서 또한 그래프의 단방향, 양방향에 대한 개념을 조금 익혀갈 수 있는 것 같다.