백준 BOJ 최단 경로 알고리즘 3가지 활용 예시 (다익스트라, 벨만-포드, 플로이드-와셜)

백준의 단계별로 풀어보기의 '최단 경로' 단계에서, 각종 최단 경로 알고리즘들을 사용하여 문제들을 풀어보도록 하겠습니다.

 

이 포스트에서 다룰 알고리즘은 순서대로 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와셜 알고리즘입니다.

백준 Online Judge에서 풀어볼 문제들은 순차적으로 BOJ 9370 : '미확인 도착지', BOJ 11657 : '타임머신', BOJ 11404 : '플로이드'입니다.

 

 

다익스트라 알고리즘 (BOJ 9370 : 미확인 도착지)

 

가장 먼저 풀어볼 문제는 다익스트라 알고리즘을 사용하는 문제입니다.

문제를 요약해보면, 정점들을 이은 간선들의 번호 및 거리가 주어지고, s에서 출발하여 g, h를 거쳐 목적지의 후보지까지 갈 때, 만약 s에서 목적지 후보까지의 거리가 같다면 그 목적지 후보들을 출력하는 문제입니다.

 

사실 이 문제는 다익스트라 알고리즘을 한 번 쓰면 끝나는 것이 아니라 구간별로 여러 번 써서 활용해야 합니다.

그래도 함수에 알고리즘이 정리되어서 구현되어 있으므로 이를 참고하시면 됩니다.

 

 

#include <bits/stdc++.h>
#define MAX 2005
using namespace std;

int n, m, t, s, g, h;
vector<pair<int, int>> adj[MAX];
vector<int> dest;
int dist_s[MAX], dist_g[MAX], dist_h[MAX];

void dijkstra(int start, int dist[MAX]) {
    for(int i=1; i<=n; i++) dist[i] = INT_MAX;
    dist[start] = 0;

    priority_queue<pair<int, int>> pQueue;
    pQueue.push({0, start});

    while(!pQueue.empty()) {
        int dist1 = -pQueue.top().first;
        int curr = pQueue.top().second;

        pQueue.pop();

        for(int i=0; i<adj[curr].size(); i++) {
            int next = adj[curr][i].first;
            int dist2 = adj[curr][i].second;

            if(dist1 + dist2 < dist[next]) {
                dist[next] = dist1 + dist2;
                pQueue.push({-dist[next], next});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    while(T--) {
        for(int i=0; i<MAX; i++) adj[i].clear();
        dest.clear();

        cin >> n >> m >> t;
        cin >> s >> g >> h;

        for(int i=0; i<m; i++) {
            int a, b, d; cin >> a >> b >> d;
            adj[a].push_back({b, d});
            adj[b].push_back({a, d});
        }

        for(int i=0; i<t; i++) {
            int x; cin >> x;
            dest.push_back(x);
        }

        dijkstra(s, dist_s);
        dijkstra(g, dist_g);
        dijkstra(h, dist_h);

        sort(dest.begin(), dest.end());
        for(int i=0; i<dest.size(); i++) {
            if(dist_s[g] + dist_g[h] + dist_h[dest[i]] == dist_s[dest[i]]) cout << dest[i] << " ";
            else if(dist_s[h] + dist_h[g] + dist_g[dest[i]] == dist_s[dest[i]]) cout << dest[i] << " ";
        }
        cout << "\n";
    }
}

 

다익스트라 알고리즘 같은 경우에는 dijkstra 함수에 모두 구현이 되어있습니다.

우선순위 큐에 시작점을 넣는 것으로 시작하여, 큐에 있는 정점들과 가장 가까이 있는 정점들을 다시 큐에 넣어줌과 동시에 거리를 갱신하면서 최단거리를 찾는 알고리즘입니다.

 

다익스트라 알고리즘을 여러 번 사용하는 이유는 가능한 경로가 g, h 순서로 거쳐서 가는 경우도 있고 h, g 순으로 거쳐서 가는 경우도 있기 때문입니다.

따라서 먼저 s에서 다익스트라 알고리즘을 사용해주고, g, h에서도 사용해서 총 3번의 다익스트라 알고리즘을 사용해야합니다.

그리고 s, g, h로부터 모든 정점까지의 거리를 기록하기 위해 dist_s, dist_g, dist_h 배열을 각각 선언해주어 여기에 값을 저장해줄 수 있도록 합니다.

 

그리고 마지막으로 목적지 후보들을 dest 벡터에 받아 정렬을 한 다음, 반복문으로 검사를 해줍니다.

이 때 가장 중요한 조건식은 : dist_s[g] + dist_g[h] + dist_h[dest[i]] == dist_s[dest[i]], 그리고 dist_s[h] + dist_h[g] + dist_g[dest[i]] == dist_s[dest[i]]와 같이 세워주면 됩니다.

 

 

벨만-포드 알고리즘 (BOJ 11657 : 타임머신)

똑같은 최단 경로 문제인데, 정점 사이를 이동하는 비용이 음수일 수가 있는 조건의 문제입니다. (문제에서는 걸리는 시간으로 두고, 음수인 경우는 시간이 과거로 돌아가는 타임머신이라고 상황이 제시되어 있습니다.)

간선의 비용이 음인 간선이 존재하는 경우, 음의 사이클이 존재하게 되면 비용을 무한히 작게 만들어버릴 수 있기 때문에 음의 사이클이 존재하는지까지 확인을 해주어야 합니다.

따라서 결국에는 정점의 수가 N개라고 할 때, N-1번의 반복적인 값의 갱신을 해주는 방법으로 최단 거리를 찾아줄 수밖에 없습니다. (그래야만 그 이후에도 값이 갱신될 경우 음의 사이클이 존재함을 확인할 수 있기 때문)

 

 

#include <bits/stdc++.h>
#define MAX 505
using namespace std;

vector<pair<pair<int, int>, int>> adj;
long long dist[MAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    for(int i=0; i<M; i++) {
        int A, B, C; cin >> A >> B >> C;

        adj.push_back({{A, B}, C});
    }

    for(int i=1; i<=N; i++) dist[i] = INT_MAX;
    dist[1] = 0;

    for(int i=1; i<=N-1; i++) {
        for(int j=0; j<adj.size(); j++) {
            int from = adj[j].first.first;
            int to = adj[j].first.second;
            int dist_ = adj[j].second;

            if(dist[from] == INT_MAX) continue;

            dist[to] = min(dist[to], dist[from] + dist_);
        }
    }

    for(int i=0; i<adj.size(); i++) {
        int from = adj[i].first.first;
        int to = adj[i].first.second;
        int dist_ = adj[i].second;

        if(dist[from] == INT_MAX) continue;

        if(dist[from] + dist_ < dist[to]) {
            cout << "-1";
            return 0;
        }
    }

    for(int i=2; i<=N; i++) {
        if(dist[i] == INT_MAX) cout << "-1" << "\n";
        else cout << dist[i] << "\n";
    }
}

 

따라서 위와 같이 시작점에서 to로 가는 비용보다 시작점 → from → to로 가는 비용이 더 작은 경우 갱신을 해주되, 이것을 N-1번 반복해주는 과정을 거칩니다.

이후 한 번 더 갱신을 돌려보면서 만약 경로가 줄어드는 구간이 나올 경우 음의 사이클이 존재하는 것이므로 그 때는 문제에서 제시한 조건대로 -1을 출력해주고, 그렇지 않은 경우에는 순차적으로 시작점으로부터 정점까지의 거리들을 출력해주면 됩니다.

 

 

플로이드-와셜 알고리즘 (BOJ 11404 : 플로이드)

이 문제의 경우에는 모든 도시 쌍 (A, B)에 대해 A에서 B로 가는 최단 거리들을 구하는 문제입니다.

플로이드-와셜 알고리즘은 이렇게 모든 정점 쌍에 대해 각 정점 사이의 최단거리들을 "모두" 구할 때 효율적인 알고리즘입니다.

 

모든 거리들을 동시에 구할 수 있다는 것은 분명 장점이지만 대신 그만큼 시간복잡도도 높은데, O(V^3)의 시간복잡도를 가지기 때문에 정점의 수가 많은 경우에는 사용하기 힘든 알고리즘입니다.

그리고 알고리즘을 막상 살펴보면 말 그대로 모든 경로에 대해 무식하게 모두 갱신해보는 방식을 사용하기 때문에 알고리즘 자체가 효율적이라고 볼 수는 없습니다.

 

 

#include <bits/stdc++.h>
#define MAX 105
using namespace std;

int dist[MAX][MAX] = {};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int n, m; cin >> n >> m;

    for(int i=0; i<m; i++) {
        int a, b, c; cin >> a >> b >> c;

        if(dist[a][b] != 0) dist[a][b] = min(dist[a][b], c);
        else dist[a][b] = c;
    }

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i != j && dist[i][j] == 0) dist[i][j] = INT_MAX;

    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(dist[i][k] != INT_MAX && dist[k][j] != INT_MAX)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(dist[i][j] == INT_MAX) cout << "0 ";
            else cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
}

 

위와 같이 k에 대해서 i → j 경로보다 i → k → j 경로가 더 짧다면 값을 갱신해주는 방식을 사용하되, 이것을 k = 1부터 n까지 모두 해보는 알고리즘입니다.

 

추가로 풀이 초반부에 dist 값을 저렇게 받는 이유는 문제에서 두 정점 사이에 간선이 여러 개 존재할 수 있다고 했기 때문입니다.

따라서 초기 간선 사이의 값을 저장할 때 더 짧은 것으로 저장해줄 필요가 있습니다.