BOJ 1504 - 특정한 최단 경로

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

다익스트라를 이용해서 푸는 문제로

특정한 조건의 노드를 반드시 거쳐야만 하는 그런 문제 였다.

오랜시간동안 고민하다 도저히 모르겠어서

다른 사람들의 코드들을 보니

다익스트라를 여러번 돌리는 것이 핵심이었다.

(PS 잘하는 사람들은 볼때 마다 놀랍다 이런 생각들은 도대체 어떻게 하는 것인지)

 

기본 다익스트라는 

"하나의 시작점에서 다른 노드들에 대한 최단 경로를 찾자" 였다면

 

이것은

1) 시작점 -> 중간 노드 A -> 중간 노드 B -> 끝점

2) 시작점 -> 중간 노드 B -> 중간 노드 A -> 끝점

에 해당하는 각각의 다익스트라를 돌렸어야 했다.

 

dijkstra(시작점, 중간 노드 A) 하면 시작점 -> 중간 노드 A 에 대한 최단 거리가 나오고

dijkstra(중간 노드 A, 중간 노드 B) 하면 중간 노드 A -> 중간 노드 B 에 대한 최단 거리가 나오고

dijkstra(중간 노드 B, 끝점) 하면 중간 노드 B -> 끝점 에 대한 최단 거리가 나와서

이를 모두 합한게 결국 최종적인 최단 거리가 된다는게 핵심이 었다

 

다만 이 연산함에 있어서 도중에 끊긴 길이 있어서 연결할 수 없는 경우 무한대 값(INF) 로 처리 되기 때문에

이에 대한 조건을 잘 달아야 문제를 통과할 수 있었다.

 

 

- c++

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#define MAX 801
#define INF 987654321
#define MIN(A, B) A > B ? B : A
 
using namespace std;
typedef pair<int, int> P;
 
int N, E, A, B, answer;
vector<pair<int, int>> adj[MAX];  // node 번호, 거리 순 으로 들어감
 
int dijkstra(int start, int end) {
    vector<int> dist(N + 1, INF);
    dist[start] = 0;
    priority_queue<P, vector<P>, greater<P>> pq;  // 거리 , 노드 번호 순으로 들어감
    pq.push(make_pair(0, start));
    while (!pq.empty()) {
        int node = pq.top().second;
        int node_distance = pq.top().first;
        pq.pop();
 
        for (int i = 0; i < adj[node].size(); i++) {
            int next_node = adj[node][i].first;
            int next_node_distance = node_distance + adj[node][i].second;
 
            if (dist[next_node] > next_node_distance) {
                dist[next_node] = next_node_distance;
                pq.push(make_pair(next_node_distance, next_node));
            }
        }
    }
    return dist.at(end);
}
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
 
    bool check1 = true;
    bool check2 = true;
 
    cin >> N >> E;
    for (int i = 0; i < E; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back(make_pair(b, c));
        adj[b].push_back(make_pair(a, c));
    }
 
    cin >> A >> B;
 
    int start_a = dijkstra(1, A);  // 1 -> A
    int a_b = dijkstra(A, B);      // A -> B
    int b_N = dijkstra(B, N);      // B -> N
 
    if (start_a == INF || a_b == INF || b_N == INF) check1 = false;  // 여기까지가 1 -> A -> B -> N 에 대한 검증
 
    int start_b = dijkstra(1, B);  // 1 -> B
    int b_a = dijkstra(B, A);      // B -> A
    int a_N = dijkstra(A, N);      // A -> N
 
    if (start_b == INF || b_a == INF || a_N == INF) check2 = false; // 여기까지가 1 -> B -> A -> N 에 대한 검증 
 
    if (check1 && check2) {
        int case1 = start_a + a_b + b_N;
        int case2 = start_b + b_a + a_N;
        answer = MIN(case1, case2);
    } else {
        answer = -1;
    }
 
    cout << answer;
 
    return 0;
}

 

 

 

 

 

- 코드 참고한 사이트

melonicedlatte.com/algorithm/2018/08/19/043431.html

[백준] 1504번 C/C++ 풀이 _ 특정한 최단 경로 - Easy is Perfect