[알고리즘 공부] 디닉 알고리즘(Dinic's Algorithm)

< 설명 >

Max flow를 구하는 데 있어, PS에서 쓸 수 있는 알고리즘 중 가장 빠르다고 한다. O(V^2 * E)의 시간복잡도를 가진다. 설명은 아래에.

 

1. BFS로 유랑이 남은 간선을 기준으로 src에서 dst 노드까지 최단 거리를 구한다.(이를 level graph라고 함)

--> BFS라서 O(E)에 가능하다. 선형 시간!

 

2. DFS로 level graph에서 blocking flow를 흘려주면서 더 이상 못 보낼 때까지 반복한다. 

--> 생각하기 좀 어려웠는데 한 번 flow를 흘려줄 때마다 bottleneck은 막혀버리니까 최소한 edge하나는 막혀버림. 그리고 edge가 막힐 때 dead end(가다가 막혀버리는 vertex)를 최대 V번 만날 수 있으므로, 많아야 VE번 증가경로를 찾고 끝난다.

 

3. 1, 2를 남은 유량이 없을 때까지 반복한다.

--> 최단 거리는 최대 모든 vertex가 다 관여할 때까지 가능하므로(V개의 vertex를 잇는 최단 거리는 최대 V-1개의 edge) V번 반복한다.

그래서 O(V) * O(VE) = O(V^2*E) 가 된다.

 

다른 좋은 블로그에서 상세한 설명은 잘 해두셔서 나는 추가로 더 참고한 유튜브 링크를 걸어두겠다.

https://www.youtube.com/watch?v=M6cm8UeeziI

 

https://www.youtube.com/watch?v=KpZjBoi_H6s

https://www.youtube.com/watch?v=UMT4Nyl8JAA

 

 

< 공부한 코드 >

** 역방향 간선을 나타내는 방식이 그전에 봤던 방식과 다르다. emplace_back을 이용해서 역방향의 idx를 맨 뒤에 저장하는 방식.

 

** DFS할 때 int& i 이렇게 reference를 하는 이유는, flow가 남는 것이 없거나 level 차이가 1을 초과하는 edge를 가볍게 건너뛰고 탐색하기 위해서이다. DFS를 여러번 반복해야하므로 애초에 의미없는 edge는 여러 번 확인하지 않는다는 의미. 그래서 level 그래프 새로 그릴 때마다 매번 새롭게 구해야 한다. 만약 그리고 edge의 용량을 남기고 종료하는 경우는 i가 증가되지 않은 채로 return이 되버리기 때문에 그 edge부터 다시 탐색하므로, 다른 경로에서 해당 edge가 사용될 수 있다. 걱정하지 않아도 된다!

 

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define pb push_back
#define N_MAX 60
#define src 0 // A
#define dst 25 // Z

int level[N_MAX]; // 레벨그래프
int checked[N_MAX]; // 이미 확인한 엣지는 확인안하기 위해서 두는 배열

struct Edge {   // u -> v
    int v, cap, rev;
    Edge(int v, int cap, int rev) :v(v), cap(cap), rev(rev) {}
};

vector<vector<Edge> > graph; // graph

// 역방향을 고려한 edge 추가
void addEdge(int a, int b, int cap) {
    graph[a].emplace_back(b, cap, (int)graph[b].size());
    graph[b].emplace_back(a, cap, (int)graph[a].size() - 1);
}    

bool bfs(){
    memset(level, -1, sizeof(level)); // level idx
    queue<int> q;
    level[src] = 0; // src의 level은 0
    q.push(src);
    while(!q.empty()){
        int here = q.front();
        q.pop();
        for (auto i : graph[here]){
            int there = i.v;
            int c = i.cap;
            if (level[there] == -1 && c > 0){ // 조건에 맞는 점들을 bfs
                level[there] = level[here] + 1;
                q.push(there);
            }
        }
    }
    if (level[dst] == -1) return false; // 도달 불가능
    else return true;
}

int dfs(int here, int bottleneck){
    if (here == dst) return bottleneck; // bottleneck이었던 유량을 return
    // 이미 확인한 edge를 반복해서 확인하기 싫어서 &i 사용
    for(int &i = checked[here]; i < graph[here].size(); i++){
        int there = graph[here][i].v;
        int c = graph[here][i].cap;
        if (level[there] == level[here]+1 && c > 0){ // 조건에 맞는 노드인가?
            int final_btn = dfs(there, min(bottleneck, c)); // 흐를 수 있는 최대유량은 최소값으로
            if (final_btn > 0) { // 끝까지 가서 찾은 final bottleneck이 유효한 값인가?
                graph[here][i].cap -= final_btn;
                graph[there][graph[here][i].rev].cap += final_btn; // 역방향 간선 고려
                return final_btn; // 이거로 탐색하다 중단하면 이 i부터 다시 시작!!
            }
        }
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    graph.resize(N_MAX);
    for(int i=0; i<N;i++){
        char a, b; int d; cin >> a >> b >> d;
        int nu, nv;
        if ('A' <= a && a <= 'Z'){
            nu = a - 'A';
        }
        else nu = a - 'a' + 26;
        if ('A' <= b && b <= 'Z'){
            nv = b - 'A';
        }
        else nv = b - 'a' + 26;
        addEdge(nu, nv, d);
    }
    int ans = 0;
    while (bfs()){ // level graph : O(V)
        memset(checked, 0, sizeof(checked));
        while(1){
            int f = dfs(src, INF); : // O(VE)
            if (f == 0) break; // 더 이상 흘려보낼 유량이 없다.
            ans += f;
        }
    }
    cout << ans << '\n';
    return 0;
}

 

오늘의 공부 끝! 시험기간인데 알고리즘 공부 너무 재밌다ㅎㅎㅎ