[C++] 백준/BOJ - 1504 : 특정한 최단 경로

문제 이해 단계

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

1504번: 특정한 최단 경로

입력으로 정점의 개수 N과 간선의 개수 E가 주어진다.
여기서 간선은 양방향 그래프이다.

정점 1에서 정점 N까지 최단경로로 움직여야 하는데,
무조건 타깃으로 설정한 정점 A와 정점 B를 방문해야 한다.

여기서는 한번 이동했던 간선도 다시 이동하는 것을 허락한다.

이러한 조건일 때 두 정점을 반드시 거치면서
최단 경로로 이동할 때의 값을 구하는 문제

정점 1에서 정점 N까지 이동할 수 없다면 -1을 출력한다.

 

---

문제 접근 단계

일단 문제에서 구하라고 하는 것은 그래프에서의 최단경로이다.
그래프 최단경로라고 하니까 다익스트라, 크루스칼, 플로이드 등 많은 알고리즘이 떠오른다.

제한사항을 살펴보면 정점의 개수는 최대 800개
간선의 개수는 최대 200,000개까지이다.

플로이드 워셜 알고리즘을 사용하기에는 정점의 개수가 너무 많다.
O(n^3)로는 반드시 시간초과가 뜬다.

여기서는 다익스트라 알고리즘을 쓰는 것이 가장 깔끔할 것 같다.

---

가능한 경로

일단 가능한 경로부터 살펴보자.

일단 출발지와 도착지는 고정되어 있다.
여기서 한 가지 의문이 들었는데,
한 정점과 다른 정점과의 최단거리 사이에는 다른 정점들이 포함되어 있을 수 있다.

그 정점에 반드시 들러야 하는 정점이
포함되어 있는지 아닌지 어떻게 판단할 수 있는가?

반드시 들러야 하는 두 정점을 t1, t2라고 하자.

정점 1에서 정점 t1으로 갈 때의 최단거리에 t2가 포함되어 있으면
t1에서 t2로 가는 비용이 필요가 없다.

그럼 중간에 반드시 들러야 하는 정점을 알아야 할까? 사실 그렇지 않다.
왜냐하면 우리가 구해야 하는 것은 최단 거리이기 때문이다.

결국 t1과 t2는 경로상 연결되어야 하기 때문에,
최단거리라면 무조건 한 번만 지나갈 것이다.

최단 거리가 아니면, 최단거리보다 무조건 비용이 높게 나올 수밖에 없다.

즉 정점 1에서 t1으로 가는 경우, 정점 1에서 t2로 가는 경우
두 경우로 구분해서 더 작은 것이 최단거리가 된다.

정점 1 → 정점 t1 → 정점 t2 → 정점 N
정점 1 → 정점 t2 → 정점 t1 → 정점 N

결론적으로 나올 수 있는 경로는 이 두 가지가 된다.

---

다익스트라

그래서 결국엔 다익스트라가 필요한데, 어떤 경로들이 필요할까?
위에서 나올 수 있는 경로들을 생각해 보면 간단하다.

정점 1이 중심인 다익스트라와
정점 t1이 중심인 다익스트라와
정점 t2가 중심인 다익스트라

이렇게 총 다익스트라를 3번만 돌리면 된다.

나머지는 문제 구현 단계에서 보도록 하겠다.

 

---

문제 구현 단계

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define INF 99999999
int N, E;
vector<pair<int,int>> v[801];
int d[801][801]; // 정점별 최단거리

// 다익스트라
void dijkstra(int num){
    // 우선순위큐로 거리가 낮은 것부터 나오도록 세팅
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    d[num][num] = 0; // 자기 자신 거리 0 
    q.push({0,num});

    while(!q.empty()){
        int x = q.top().second; // 출발 정점
        int cost = q.top().first; // 현재 비용
        q.pop();
        // 연결된 정점을 모두 살펴봄
        for(int i = 0; i < v[x].size(); i++){
            int nx = v[x][i].first; // 연결된 정점
            int nCost = v[x][i].second + cost; // 연결된 정점으로 갔을때의 비용

            
            if(d[num][nx] > nCost){
                // 저장된 최단거리보다 더 작은 경우 갱신하고 큐에 넣음
                d[num][nx] = nCost;
                q.push({nCost,nx});
            }
        }
    }
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> N >> E;
    for(int i = 0; i < E; i++){
        int a,b,len;
        cin >> a >> b >> len;
        v[a].push_back({b,len});
        v[b].push_back({a,len});
    }
    int t1,t2;
    cin >> t1 >> t2;
    fill(&d[0][0],&d[800][801],INF);

    // 다익스트라를 총 3번 돌림
    dijkstra(1);
    dijkstra(t1);
    dijkstra(t2);


    // 두가지 경우의 수 중 더 작은 것
    long long val1 = d[1][t1] + d[t1][t2] + d[t2][N];
    long long val2 = d[1][t2] + d[t2][t1] + d[t1][N];

    // INF보다 크거나 같으면 도달에 실패했다는 것
    long long ans = min(val1,val2);
    if(ans >= INF) cout << "-1";
    else cout << ans;
}

우선순위 큐를 통해 다익스트라 알고리즘을 구현하였다.
거리가 낮은 것부터 나오도록 내림차순으로 정렬하였다.

다익스트라는 정점 1, t1, t2에 대해서만 돌렸다.
다익스트라를 모두 돌린 후, 위에서 설명했던 경로대로 값을 구해준다.

둘 중 더 작은 값이 답이 된다.
long long으로 해줬는데 int로만 해줘도 답이 된다. 

INF보다 크거나 같다는 것은
값이 N에 도달하지 못했다는 뜻이므로 -1을 반환한다.

 

---

시행착오

다익스트라 알고리즘이라는 것을 파악하고,
거의 다 풀었는데 시간초과가 떴다.

원인은 모든 정점에서의 최단거리를 구해준 것..
다익스트라를 딱 3번만 돌리면 되는데
최악의 경우 800개가 되는 정점을 모두 구해주려고 했다.

이래서 시간 초과가 떴다.. 좀 더 생각하자.

https://toss.me/howudong

howudong님에게 보내주세요