디닉 알고리즘(Dinic's Algorithm)

---

목차

1. 디닉 알고리즘(Dinic's Algorithm)이란?

2. 디닉 알고리즘(Dinic's Algorithm) 구현 방법

3. 디닉 알고리즘(Dinic's Algorithm) 시간 복잡도

4. 디닉 알고리즘(Dinic's Algorithm) 소스 코드

5. 디닉 알고리즘(Dinic's Algorithm) 관련 문제

---

1. 디닉 알고리즘(Dinic's Algorithm)이란?

이전 포스팅에서는 네트워크 플로우를 위해 애드몬드 카프, 포드 풀커슨 방법을 이용하였다.

애드몬드 카프 방법은 O(V*E^2)으로써 다양한 네트워크 플로우 문제를 해결하는데 이용된다.

하지만 간혹가다 간선의 수가 상당히 많은 문제를 만나게 되면 O(V*E^2)으로 해결 할 수 없는 문제가 있을 수 있다.

그때를 위한 디닉 알고리즘(Dinic's Algorithm)을 공부해보고자 한다.

참고로 디닉은 O(V^2*E)의 복잡도를 가진다.

2. 디닉 알고리즘(Dinic's Algorithm) 구현 방법

디닉 알고리즘을 구현하기 위해 아래 두 개념을 알아야 한다.

(아래에서 나타는 그래프는 wiki의 그래프를 이용하였습니다. :: https://en.wikipedia.org/wiki/Dinic%27s_algorithm)

1. 레벨 그래프(Level Graph) :: 모든 정점에 대해 레벨을 매겨놓은 그래프를 의미한다. 이때 레벨을 매기는 기준은 다음과 같다.

Source가 되는 정점은 레벨이 0이고, 소스와 인접한 정점들은 레벨이 1, 레벨 1 정점과 인접한 정점들은 레벨이 2, ..., 레벨 n - 1 정점과 인접한 마지막 Sink의 레벨은 n이 된다.

레벨 그래프를 형성하는 조건은 다음과 같다.

1) 해당 정점은 아직 레벨을 부여받지 않은 정점이어야 한다.

2) c[here][next] - f[here][next] > 0. 즉, here에서 next로 유량이 흐를 수 있는 간선만을 이용할 수 있다.

2. 차단 유량(Blocking Flow) :: 레벨 그래프를 형성할 때 레벨 그래프를 형성하는 조건에 맞지 않는 간선들을 제외한 것들을 의미한다.

위와 같은 그래프가 있다고 생각해보자.

이 그래프의 레벨 그래프는 아래와 같이 표현할 수 있다.

주황색으로 칠해진 간선은 실제 레벨 그래프를 형성할 때 조건에 해당하는 간선이 될 것이다.

(예를들어 1과 1사이 간선은 이미 1이라는 레벨이 형성되었기에 조건 1을 만족하지 못한다.)

이러한 주황색 간선으로만 이루어진 유량들을 차단 유량이라고 한다.

이제 위의 과정에서 유량을 흘러보내면 다음과 같이 형성된다.

위의 레벨 그래프로 흘러보낸 유량의 총 합은 14가 되므로, 14를 결과값에 더해준다.

다시 레벨 그래프를 만들면 다음과 같다.

하늘색 간선은 왜 생긴거죠?

하늘색 간선은 네트워크 플로우의 성질에서 flow에 해당하는 보이지 않는 간선이다.

즉 3->2로 6의 유량을 보낸적이 있으니 반대로 2->3으로는 -6의 유량을 보냈다는 것이다.

3. 유량의 대칭성 :: f(u,v) = -f(u,v)  << http://www.crocus.co.kr/741 >>

이제 위의 주황색, 하늘색의 간선을 이용하여 차단 유량에서의 유량을 흘려보자.

추가적으로 5만큼의 유량이 더 흘렀다. 따라서 총합은 14 + 5인 19가 된다.

위의 과정을 거치고 난 후, 또 레벨 그래프를 형성해보자.

이번에는 레벨 그래프가 0과 1밖에 생성되지 않았고, sink까지 레벨이 제대로 형성되지 않았다.

이때 디닉 알고리즘은 종료 조건을 만족하게 되고, 최대 유량은 19라는 것을 알 수 있게 된다.

3. 디닉 알고리즘(Dinic's Algorithm) 시간 복잡도

Dinic's Algorithm은 최단 경로를 이룰 수 있는 간선들을 명시적으로 그래프로 만든 후, O(VE) 시간 안에 가능한 flow를 모두 흘려준다. 

초기에 bfs로 최단 경로를 이룰 수 있는 그래프만을 추출하고 (이를 Level Graph라고 한다), 이후 dfs로 O(E)번 증가 경로를 찾는데 찾는 과정에서 만약에 포화된 간선이 존재한다면 그 간선을 그래프에서 제거한다.

고로, 각각의 간선은 증가 경로의 일부로 작동하거나, 한번 사라져서 다시 보지 않게 된다. 

증가 경로의 길이는 길어야 V이니 증가 경로의 일부로 작동하는 횟수는 VE, 삭제되는 횟수는 E이다. 

고로 O(VE) 안에 해당 최단 경로에서 가능한 flow를 모두 보낸 것이다. 이것이 O(V) 번 반복되어서, 시간 복잡도는 O(V^2E)가 된다.

출처 :: http://koosaga.com/18

4. 디닉 알고리즘(Dinic's Algorithm) 소스 코드

[2367번] 파티 :: http://www.crocus.co.kr/1070

위 문제를 통해 디닉 알고리즘을 이용해보자.

위 문제에 대한 전반적인 설명은 위의 링크에 모두 기술되어있다.

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <memory.h>
#include <algorithm>
 
#define fastio() ios::sync_with_stdio(0),cin.tie(0);
 
using namespace std;
 
const int MAX_V = 502;
const int INF = 987654321;
const int FOOD = 250;
 
int c[MAX_V][MAX_V];
int f[MAX_V][MAX_V];
int work[MAX_V];
int level[MAX_V];
 
 
vector<int> adj[502];
 
int S = 0, T = 500;
 
 
// 디닉 bfs
bool bfs()
{
    fill(level, level + MAX_V, -1);
 
    level[S] = 0;
 
    queue<int> q;
 
    q.push(S);
 
    while (!q.empty())
    {
        int here = q.front();
        q.pop();
 
        for (int i = 0; i < adj[here].size(); i++)
        {
            int next = adj[here][i];
 
            if (level[next] == -1 && c[here][next] - f[here][next] > 0)
            {
                level[next] = level[here] + 1;
                q.push(next);
            }
        }
    }
 
    return level[T] != -1;
}
 
// 디닉 dfs
int dfs(int here, int flow)
{
    if (here == T)
        return flow;
 
    for (int &i = work[here]; i < adj[here].size(); i++)
    {
        int next = adj[here][i];
 
        if (level[next] == level[here] + 1 && c[here][next] - f[here][next] > 0)
        {
            int ret = dfs(next, min(c[here][next] - f[here][next], flow));
 
            if (ret > 0)
            {
                f[here][next] += ret;
                f[next][here] -= ret;
 
                return ret;
            }
        }
    }
 
    return 0;
}
 
int main()
{
    int n, k, d;
    cin >> n >> k >> d;
 
    for (int i = 1; i <= n; i++)
    {
        c[S][i] = k;
 
        adj[S].push_back(i);
        adj[i].push_back(S);
    }
 
    for (int i = 1; i <= d; i++)
    {
        int val;
        cin >> val;
 
        c[i + FOOD][T] = val;
        adj[i + FOOD].push_back(T);
        adj[T].push_back(i + FOOD);
    }
 
    for (int i = 1; i <= n; i++)
    {
        int cnt;
        cin >> cnt;
 
        for (int j = 0; j < cnt; j++)
        {
            int pos;
            cin >> pos;
 
            c[i][pos + FOOD] = 1;
 
            adj[i].push_back(pos + FOOD);
            adj[pos + FOOD].push_back(i);
        }
    }
 
 
    int totalFlow = 0;
 
    while (bfs())
    {
        fill(work, work + MAX_V, 0);
 
        while (1)
        {
            int flow = dfs(S, INF);
            if (flow == 0)
                break;
            totalFlow += flow;
        }
    }
 
    cout << totalFlow;
 
    return 0;
}
 
 

우선 bfs부분을 보면 레벨 그래프를 형성하는 간단한 bfs 코드이다.

이때 레벨 그래프를 형성하는 조건을

if (level[next] == -1 && c[here][next] - f[here][next] > 0)

위의 코드에서 확인 할 수 있다.

이제 dfs부분을 보면 유량을 흘러보내는 과정을 파악할 수 있다.

이때 중점을 두고 봐야할 코드는 work 배열이다.

for (int &i = work[here]; i < adj[here].size(); i++)

i는 work[here]을 참조하고 있게되고 i가 증가할때마다 i가 work[here]을 참조하니 work[here]의 값도 +1씩 증가하게 된다.

이 의미는 만약 어떤 레벨그래프 차단 유량에서 S->1->2->T로 유량을 흘려보냈다고 생각해보자.

(S->1 은 5/100, 1->2는 5/100, 2->T는 5/5의 flow/capacity를 보냈다고 생각해보자.)

그러면 그다음 또 유량을 흘려 보낼 때 같은 레벨 그래프내에서는 S->1->2->T는 이미 최대 유량을 흘려보냈을 것이고,

2->T는 5/5 즉, 유량을 최대로 보낸 상태이기에 이 간선을 통해서 보낼 수 있는 유량은 더이상 없다는게 자명해진다.

이러한 것을 메모하기 위해 work배열이 생성된 것이고, work배열은 현재 노드가 몇번째 간선부터 보면 될지 파악해주는 역할을 하게 된다.

참조를 하는 코드를 풀어서 쓰면 다음 코드와 동치이다.

int dfs(int here, int flow)
{
    if (here == T)
        return flow;
 
    for (int i = work[here]; i < adj[here].size(); i++)
    {
        int next = adj[here][i];
 
        if (level[next] == level[here] + 1 && c[here][next] - f[here][next] > 0)
        {
            int ret = dfs(next, min(c[here][next] - f[here][next], flow));
 
            if (ret > 0)
            {
                f[here][next] += ret;
                f[next][here] -= ret;
 
                work[here] = i;
                return ret;
            }
        }
    }
 
    work[here] = adj[here].size();
    return 0;
}
 
 

이제 메인 함수부분을 보면 while(bfs())에서 레벨 그래프가 형성되지 않을 때 까지 반복을 하고,

생성된 레벨 그래프의 차단 유량 내에서 최대 유량을 구해준다.

그 구한 값을 결과값에 더하는 과정을 반복하게 된다.

5. 디닉 알고리즘(Dinic's Algorithm) 관련 문제

사실상 모든 네트워크 플로우 문제를 디닉으로 풀면 된다.

http://www.crocus.co.kr/search/%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC%20%ED%94%8C%EB%A1%9C%EC%9A%B0