그래프 - 최단 경로(BFS, 다익스트라, 벨만-포드, 플로이드-와샬)

해당 도서와 블로그의 내용을 공부해 정리한 것입니다.

http://www.yes24.com/Product/Goods/8006522

알고리즘 문제 해결 전략 세트 - YES24

http://www.yes24.com/Product/Goods/72274740

알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드 - YES24

https://anz1217.tistory.com/23

최단 경로

 

최단 경로

두 정점을 연결하는 경로 중 길이가 가장 짧은 경로

BFS, 다익스트라, 벨만-포드는 시작 정점에서 존재하는 다른 모든 정점들로 도달하는 최단 경로를 구하는 알고리즘이다.

 

 

BFS 최단경로

BFS로 문제를 푼다면 거의 최단 경로, 특히 가중치가 없는 그래프에서의 최단 경로를 구하는 문제를 해결하게 된다. 그래프의 최단 경로를 DFS로 해결하려 하면, 정점과 간선이 많으면 많을수록 최단 경로를 빠르게 구하기 힘들어지기 때문이다. 대신 구현이 쉽고 간편한 만큼 다른 그래프 문제를 풀 때에는 DFS를 많이 사용하게 된다.

 

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

18352번: 특정 거리의 도시 찾기

일반적인 BFS에서, 시작 정점에서 현재 정점까지 도달하는 데까지의 거리를 저장하는 배열 \(dist\)를 만들면 된다. 인접한 정점의 거리는 (현재 정점의 거리 + 1)을 해주면 된다.

이때 \(dist\)를 절대 될 수 없는 값 -1로 초기화한다면, \(dist\)가 -1일 때는 아직 방문하지 않은 정점일 것이므로 \(vis\) 배열 대신 방문 여부를 처리할 수 있다.

#include <bits/stdc++.h>
#define inf 1e9
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N, M, K, X;
vector<int> graph[300001];
queue<int> qu;
int dist[300001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> M >> K >> X;
    for (int i{1}; i <= M; i++)
    {
        int A, B;
        cin >> A >> B;
        graph[A].push_back(B);
    }

    memset(dist, -1, sizeof(dist));

    qu.push(X);
    dist[X] = 0; //처음 거리는 0
    while (!qu.empty())
    {
        int u = qu.front();
        qu.pop();

        for (int v : graph[u])
        {
            if (dist[v] != -1)
                continue;

            qu.push(v);
            dist[v] = dist[u] + 1;
            //인접한 정점의 거리는 (현재 정점의 거리 + 1)
        }
    }

    vector<int> ans;
    for (int i{1}; i <= N; i++)
        if (dist[i] == K)
            ans.push_back(i);

    sort(ans.begin(), ans.end());
    if (!ans.size())
        cout << -1 << "\n";
    else
        for (int u : ans)
            cout << u << "\n";
}

 

굳이 인접 리스트를 만들지 않아도 될 때가 있는데, 다음 문제가 그렇다.

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

2178번: 미로 탐색

문제의 미로를 그래프로 만든다면, 각 정점 vector에 저장된 원소들은 해당 정점의 상하좌우에 있는 정점이 된다. 상하좌우에 있는 정점은 현재 정점의 좌표를 더하거나 빼는 것만으로도 도달할 수 있다. 따라서 이 문제는 굳이 인접 리스트를 통해 그래프를 만들 필요 없이, 방향을 나타내는 \(dir\) 배열을 구현하기만 하면 된다. 단, 상하좌우의 인접한 정점에 접근할 때 index 범위를 벗어나지 않도록 주의하자. 자주 나오는 유형이므로 기억하면 좋다.

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N, M;
char maze[101][101];
queue<pii> qu;
int dir[2][4] = {{-1, 1, 0, 0}, {0, 0, -1, 1}}; //상하좌우에 접근하는 배열
int dist[101][101]; //각 좌표까지 도달하는 데까지의 거리

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> M;
    for (int i{1}; i <= N; i++)
        for (int j{1}; j <= M; j++)
            cin >> maze[i][j];
            
    memset(dist, -1, sizeof(dist));

    qu.push({1, 1});
    dist[1][1] = 1; //처음 거리는 1
    while (!qu.empty())
    {
        auto [cx, cy] = qu.front();
        qu.pop();

        for (int i{0}; i < 4; i++)
        {
            int nx = cx + dir[0][i];
            int ny = cy + dir[1][i];
            //인접한 좌표

            if (nx >= 1 && nx <= N && ny >= 1 && ny <= M)
            //인접한 좌표가 index 범위 내에 있는지 확인
            {
                if (dist[nx][ny] != -1 || maze[nx][ny] == '0')
                    continue;

                qu.push({nx, ny});
                dist[nx][ny] = dist[cx][cy] + 1;
            }
        }
    }
    cout << dist[N][M] << "\n";
}

 

 

0-1 BFS

간선의 가중치가 0 또는 1일 때만 사용할 수 있는 최단경로 알고리즘이다.

간선의 가중치가 1일 때는 뒤에 push하지만, 0일 때는 앞에 push하면 된다.

때문에 이 알고리즘에서는 queue가 아닌 deque를 쓴다.

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

13549번: 숨바꼭질 3

순간이동을 할 때는 가중치 0, 그 이외에는 가중치 1이므로, 다음 정점이 범위에 벗어나는지를 확인하며 deque에 push해주면 된다.

처음 찾은 경로가 최단 경로가 아닐 수 있기에, \(dist\) 배열의 최단 경로를 매번 비교해야 한다.

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N, K;
int dist[100001];
deque<int> dq;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> K;
	
	fill(dist, dist + 100001, sizeof(dist));
	
	dq.push_back(N);
	dist[N] = 0;
	while(!dq.empty())
	{
	    int u = dq.front(); dq.pop_front();
	    
	    if(u+1<=100000 && dist[u] + 1 < dist[u+1])
	    {
	        dq.push_back(u+1);
	        dist[u+1] = dist[u] + 1;
	    }
	    
	    if(u-1>=0 && dist[u] + 1 < dist[u-1])
	    {
	        dq.push_back(u-1);
	        dist[u-1] = dist[u] + 1;
	    }
	    
	    if(u*2<=100000 && dist[u] < dist[u*2])
	    {
	        dq.push_front(u*2);
	        dist[u*2] = dist[u];
	    }
	}
	
	cout << dist[K];
}

 

 

다익스트라 알고리즘

간선의 가중치가 음수가 아닐 때 사용할 수 있는 최단경로 알고리즘

BFS 최단경로 알고리즘과 유사하지만 차이점이 몇 가지 존재한다.

 

1. a -> x -> y -> b로 가는 경로가 a -> b로 가는 최단 경로라면, a -> x -> y로 가는 경로는 a -> y로 가는 경로의 최단경로이다. a -> x -> y로 가는 경로가 a -> y로 가는 경로의 최단경로가 아니라 가정해보자. 그렇다면 이보다 더 큰 거리로 a -> y로 이동해야 하는데, y -> b로 가는 경로는 고정되어 있다. 따라서 이 가정은 거짓이다. 이 사실로부터 알 수 있는 것은, 시작점으로부터 거리가 가장 짧은 정점에서부터 인접한 정점의 거리를 완화시켜나간다면, 언젠가는 도착점의 최단 거리를 구할 수 있다는 것이다. 거리를 완화시킨다는 뜻은, \(dist\)에 저장된 다음 정점까지의 거리가 현재 정점에서 다음 정점까지 이동한 총 거리보다 길 때 거리를 후자로 바꾼다는 뜻이다. 따라서 다익스트라 알고리즘은 이와 같은 방식을 따른다.

 

2.  BFS에서는 queue에 정점 정보만 저장하였지만, 다익스트라에서는 오름차순 priority_queue를 이용해 (가중치, 정점) pair 형태로 저장한다. 이렇게 저장하면 가중치가 가장 작은 정점이 top에 존재하기에, top에서 BFS 최단경로처럼 인접한 정점을 탐색하며 거리를 완화시키면 된다.

 

3. BFS 최단경로와 마찬가지로, 다익스트라 역시 방문 처리를 정점까지의 거리를 저장하는 배열 \(dist\)로 대체한다. 대신 BFS는 \(dist\)를 -1로 초기화했지만, 다익스트라에서는 절대 도달할 수 없는 값인 아주 큰 값 inf로 초기화한다. 만약 -1로 \(dist\) 배열을 초기화했다면 방문 처리와 거리 비교를 따로 해야 하지만, inf로 초기화할 경우 이 둘을 한 번에 처리할 수 있다.

 

4. 정점 a, b, c가 있다고 해보자. a -> c로 가는 경로로 \(dist[c]\)를 완화했는데, b -> c로 가는 경로가 더 짧아 다시 \(dist[c]\)를 완화했다면 어떻게 될까? \(dist[c]\)는 b -> c 경로의 가중치로 완화된 상태인데, priority_queue에는 a -> c 경로의 가중치와  b -> c 경로의 가중치가 동시에 들어있다. 다익스트라는 priority_queue가 empty 상태일 때까지 동작하므로, 언젠가는 a -> c 경로의 가중치가 top에 도달하게 될 것이며, 그렇게 된다면 제대로 된 최단경로를 구할 수 없을 것이다. 이를 방지하기 위해 top의 가중치와 \(dist\) 배열에 저장된 값을 비교하여, top의 가중치가 더 크다면 이 정보를 무시한다.

 

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

1753번: 최단경로

#include <bits/stdc++.h>
#define inf 1e9
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int V, E, K;
vector<pii> graph[20001];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int dist[20001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> V >> E >> K;
    for (int i{1}; i <= E; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({w, v});
    }

    fill(dist, dist + V + 1, inf); //dist 초기화

    dist[K] = 0;
    pq.push({dist[K], K});
    while (!pq.empty())
    {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u])
            continue; //거리가 dist와 다르면 무시

        for (auto [d, v] : graph[u])
        {
            if (dist[v] > dist[u] + d)
            {
                dist[v] = dist[u] + d;
                pq.push({dist[v], v});
            } //두 거리를 비교해 현재 정점으로부터의 거리가 더 짧으면 완화
        }
    }

    for (int i{1}; i <= V; i++)
    {
        if (dist[i] == inf)
            cout << "INF\n";
        else
            cout << dist[i] << "\n";
    }
}

BFS와 마찬가지로 모든 정점과 간선을 탐색하지만, 간선을 탐색할 때 간선의 수만큼 priority_queue에 push하는 작업을 수행한다. 정점 수를 \(E\), 간선 수를 \(V\)라 할 때, priority_queue의 push 수행 시간은 \(O(logV)\)이므로 다익스트라의 시간복잡도는 \(O(E + VlogV)\)이다.

 

만약 간선의 가중치가 음수라면 다익스트라 알고리즘이 제대로 동작하지 못한다. 아래 그림에서 다익스트라 알고리즘을 적용한다면, 가중치가 작은 간선을 택할 것이기 때문에 1 + 7 = 8로 오른쪽 정점의 거리가 결정된다. 하지만 실제 최단경로는 5 + (-4) = 1이다.

 

또한, 다음과 같이 사이클 전체 가중치 합이 음수인 경우, 다익스트라 알고리즘에서는 무한 루프를 돌게 된다.

 

 

 

벨만-포드 알고리즘

간선의 가중치가 음수일 때도 사용할 수 있는 최단경로 알고리즘

다익스트라가 시작점으로부터 거리가 가장 짧은 정점에서 인접한 정점들을 완화시킨다면, 벨만-포드는 모든 정점에 대하여 인접한 정점의 완화를 시도한다. 단, 인접한 정점을 완화할 때는 현재 정점이 한 번은 방문되어 있어야 한다.

한 정점에서 다른 정점까지 거치는 간선의 최대 수는 (정점의 수 - 1)이다. 때문에 모든 정점에 대하여 인접한 정점의 완화를 시도하는 작업을 (정점의 수 - 1)번 반복하면, 존재하는 모든 정점에 대해 최단경로를 구할 수 있다.

만약 (정점의 수 - 1)번을 초과해 이 작업을 시행했는데도 간선 완화가 일어났다면, 그래프에 시작 지점에서 출발하여 도달할 수 있는 음수 사이클이 존재한다는 뜻이다. 음수 사이클이 존재한다 해도 시작 지점과 분단되어 있다면 음수 사이클의 존재 여부를 알 수 없다. 애초에 완화 자체가 일어나지 않기 때문이다.

 

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

11657번: 타임머신

이 문제에서 음수 사이클이 존재한다면 \(dist\)의 범위가 \(NMC\)가 된다. 따라서 long long으로 \(dist\)를 선언해주자.

#include <bits/stdc++.h>
#define inf 1e9
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N, M;
vector<pll> graph[501];
ll dist[501];
bool isCycle = false;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> M;
    for (int i{1}; i <= M; i++)
    {
        int A, B, C;
        cin >> A >> B >> C;
        graph[A].push_back({C, B});
    }

    fill(dist, dist + N + 1, inf);

    dist[1] = 0;
    for (int i{1}; i <= N; i++)
    {
        bool update = false; // 경로 완화 확인
        for (int u{1}; u <= N; u++)
        {
            for (auto [d, v] : graph[u])
            {
                if (dist[u] != inf && dist[v] > dist[u] + d)
                {
                    dist[v] = dist[u] + d;
                    update = true;
                } // 한 번은 완화된 정점이며, 이 정점에서 다음 정점을 완화할 수 있다면
            }
        } // 모든 정점의 간선에 대해 완화를 시도한다.

        if (i == N && update)
            isCycle = true;
        // N번째 시행에서도 완화되었다면 음수 사이클이 존재한다는 뜻이다.

        // if (!update) break; - 정점 완화가 안 되었다는 것은 모든 정점이 완화되었다는 뜻이므로 break해도 된다.
    } // 이 방식을 N번 반복

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

 

벨만-포드를 최적화한 알고리즘으로 SPFA 알고리즘이 있다. 벨만-포드는 모든 정점에 대하여 인접한 정점의 완화를 시도하지만, SPFA 알고리즘은 인접한 정점을 완화할 수 있는 정점에 한하여 인접한 정점의 완화를 시도하기에 평균적으로 벨만-포드보다 더 빠르다. 단 최악의 경우에는 벨만-포드와 시간복잡도가 같다.

인접한 정점을 완화할 수 있는 정점에 한하여 인접한 정점의 완화를 시도하기에, BFS 최단경로와 동작 방식이 비슷하다. BFS 최단경로 알고리즘에 거리 완화 코드를 추가한 것이라 생각해도 된다. 차이점은, BFS와 달리 SPFA는 방문한 정점을 다시 방문할 수 있다. 정점이 완화되었다 해도 그 정점을 또 방문하기에 \(dist\) 배열로 방문 처리를 할 수 없어, 인접한 정점이 queue에 있다는 것을 말하는 \(inQueue\) 배열을 사용한다. 인접한 정점이 queue에 있다면 완화만 하고, 없다면 queue에 push하는 것이다.

어떤 정점을 존재하는 정점 수 이상 방문하면 음수 사이클이 존재한다는 뜻이다. 이 경우 break한다.

#include <bits/stdc++.h>
#define inf 1e9
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int N, M;
vector<pll> graph[501];
ll dist[501];
queue<int> qu;
bool inQueue[501];
int vis[501];
bool isCycle = false;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> M;
    for (int i{1}; i <= M; i++)
    {
        int A, B, C;
        cin >> A >> B >> C;
        graph[A].push_back({C, B});
    }

    fill(dist, dist + N + 1, inf);

    dist[1] = 0;
    qu.push(1);
    inQueue[1] = true;
    while (!qu.empty())
    {
        int u = qu.front();
        qu.pop();
        inQueue[u] = false;

        if (++vis[u] >= N)
        {
            isCycle = true;
            break;
        } // 어떤 정점을 방문한 횟수가 정점 개수 이상이라면 음수 사이클이 존재한다.

        for (auto [d, v] : graph[u])
        {
            if (dist[v] > dist[u] + d)
            {
                dist[v] = dist[u] + d;

                if (!inQueue[v])
                {
                    qu.push(v);
                    inQueue[v] = true;
                } // 이미 queue 내에 있는 정점은 또 push할 필요 없이 완화만 시켜주면 된다.
            }
        }
    }

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

벨만-포드 알고리즘은 모든 정점에 대해 인접한 정점의 완화를 시도하므로, 이 작업은 간선의 수만큼 걸린다. 그리고 이 작업을 존재하는 노드 수만큼 시행한다. 정점의 수를 V, 간선의 수를 E라 하면 시간복잡도는 \(O(VE)\)이다.

SPFA 알고리즘의 경우 최악의 경우 \(O(VE)\)이지만 평균적으로 \(O(E)\) 시간에 수행된다 알려져 있다.

 

 

플로이드 알고리즘

모든 정점 간의 최단 경로를 구하는 알고리즘

어떤 정점 \(i\)에서 \(j\)로 이동할 때, 1 ~ \(k\)까지만을 경유할 수 있는 정점이라 할 때 그 최단경로를  \(dist[k][i][j]\)라 하자.

그렇다면 이를 구하기 위해 1부터 k까지 경유 정점으로 설정해 전부 구해야 할까? 어떤 정점 \(i\)에서 \(j\)로 이동할 때, 1 ~ \(k - 1\)까지만을 경유할 수 있는 정점이라 할 때 그 최단경로는 \(dist[k - 1][i][j]\)이다. 즉 경유 정점이 1 ~ \(k - 1\)인 경우는 이미 알고 있다. 따라서 \(dist[k][i][j]\)는 다음 두 경우만 비교하면 된다.

 

1. 경유 정점이 1 ~ \(k - 1\)일 때, 정점 \(i\)에서 \(k\)로 이동하는 경로 + 정점 \(k\)에서 \(j\)로 이동하는 경로

즉, 정점 \(k\)를 경유하는 경로 \(dist[k - 1][i][k] + dist[k - 1][k][j]\)

2. 어느 정점도 경유하지 않는 경로 \(dist[k - 1][i][j]\)

 

이를 점화식으로 표현하면

$$ dist[k][i][j] = min(dist[k-1][i][k] + dist[k-1][k][j], dist[k-1][i][j]) $$

이다. 그런데 \(dist[k][][]\)는 \(dist[k-1][][]\)에만 의존하므로, \(k = 1, 2, 3, ...\) 순으로 bottom - up 방식으로 \(dist\)를 처리할 수 있다. 이를 구현한 것이 아래 코드이다.

#include <bits/stdc++.h>
#define inf 1e9
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

int n, m;
int dist[101][101];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    fill(&dist[0][0], &dist[100][100], inf);
    for (int i{1}; i <= n; i++)
        dist[i][i] = 0;

    for (int i{1}; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], c);
    }

    for (int k{1}; k <= n; k++)
        for (int i{1}; i <= n; i++)
            for (int j{1}; j <= n; j++)
                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] == inf)
                cout << 0 << " ";
            else
                cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
}

bottom - up 동적계획법을 실행하는 데 삼중 반복문을 사용하므로, 정점의 수를 \(V\)라 하면 시간복잡도는 \(O(V^{3})\)이다. 그렇기 때문에 정점의 개수가 적은 경우에 한해서만 이 알고리즘을 쓸 수 있다. 단 정점 개수가 충분히 작으면 모든 정점 간의 최단 경로를 구하기 위해 다익스트라나 벨만-포드를 정점의 개수만큼 반복하는 것보다 효율적이고, 구현도 쉽다.