백준 17412 도시 왕복하기 1 c++ / Dinic 알고리즘

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

 

도시 정보가 주어져 있을 때, 1번이 source, 2번이 sink인 그래프에서 최대 유량을 구하는 문제와 동일합니다. 

1번에서 2번으로 가는 최대 경로 개수는 결국 모든 엣지의 cap이 1인 상황에서 최대 유량을 구하는 것과 동일합니다. 

 

최대 유량을 구하는 기법 중 빠른 것으로 알려진 Dinic 알고리즘을 적용해보았습니다. Dinic 알고리즘에 대한 설명 및 구현은 아래 글들을 참고하였습니다. 

https://gazelle-and-cs.tistory.com/84

디니츠의 알고리즘 (Dinitz' Algorithm)

https://www.crocus.co.kr/1088

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

 

Dinic 알고리즘은 다음과 같이 동작합니다. 

 

1. level graph 구성 (bfs)

level graph는 source로부터 현재 그래프의 최단 거리(level)가 동일한 노드를 동일한 레벨로 잡은 서브 그래프입니다. 레벨 그래프를 따라 이동하면 결국 sink까지 현재 state에서 최단 거리로 이동할 수 있으며, 레벨 그래프를 이용해 2번의 blocking flow 찾기 방식으로 최단 거리를 따라 유량을 흘려보냅니다. level graph를 구성하는 방식은 다음과 같습니다.

 

- source로부터 bfs를 이용해 각 노드까지 최단 거리를 계산합니다. 이 때 해당 거리를 레벨로 잡으면, 결국 레벨이 동일한 노드들로 묶을 수 있습니다. 

- 단, 가능한 cap이 0보다 큰 엣지를 대상으로만 탐색합니다. (0인 곳은 어짜피 유량 못 흐르므로) 

- 그리고 레벨 계산 시, sink보다 더 뒤에 있는 케이스도 있을 수 있으므로, 레벨 그래프에서의 이동은 반드시 레벨이 증가하는 방향 (최단 거리)를 따라 이동합니다. 

 

2. blocking flow 찾기 (dfs)

blocking flow는 말 그대로 막히는 흐름을 찾는 것입니다. 유량을 보내면 어느 순간 cap이 다 차는 지점이 나올 것이고, 그 이후로는 최단 경로를 따라 이동하더라도 결국 해당 증강 경로의 유량은 0이기 때문에 굳이 더 탐색할 필요가 없습니다. blocking flow를 찾음으로써 최대 유량을 갱신하는 방법은 다음과 같습니다. 

 

- 레벨 그래프를 이용해 dfs를 사용하여 source에서 sink까지 유량을 보낼 수 있는 증강 경로를 찾습니다. 

- 이 때 증강 경로를 레벨 그래프를 따라 dfs로 탐색을 하므로, 해당 증강 경로에 대한 최대 유량 (지나온 엣지의 가용 cap의 최소값) 을 dfs 계산과 동시에 처리할 수 있습니다. 

- 이를 blocking flow가 없을 때까지 반복합니다. (즉, 탐색한 최종 유량이 0인 경우)

 

3. 최대 유량 계산

1,2번을 이용해 최대 유량을 계산하는 방식은 아래와 같습니다. 

- level graph 계산

- blocking flow 찾기 기법을 이용해 최대한 유량을 흘려보낸다. 

- 계산된 유량을 최대 유량 값에 계속 추가한다. 

- 더 이상 sink까지 도달하는 경로가 없으면 (즉, sink까지 가는 모든 경로 상에 0이 있는 경우 == sink까지 가는 경로가 없는 경우 == sink의 레벨 그래프가 업데이트되지 않는 경우) 종료한다. 

 

gazelle 님의 블로그에 그래프 이론, 조합론 관련된 좋은 설명들이 많으니 추천드립니다. (아마 없었으면 원서를 뒤졌어야 됐을 거 같다.....) 

 

17412번에 대한 코드는 아래와 같습니다. 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N, P;
// source 1, sink 2

struct Edge {
    int to;
    int rev; // 역방향 기준 몇 번째 엣지인지 
    int cap;
    int flow;
};

vector<Edge> graph[401];
vector<int> level; // level graph에서 몇 번 level인지 (using bfs)
vector<int> iter; // blocking flow에서 몇 번째까지 탐색했는지 (using dfs)

const int SOURCE = 1;
const int SINK = 2;

const int INF = 987654321; // 문제 상에서 edge 최대 10,000개, cap 모두 1 

void init() {
    cin >> N >> P;

    level.resize(N + 1);
    iter.resize(N + 1);
    
    int from, to;
    for(int i = 0; i < P; i++) {
        cin >> from >> to;
        Edge e = {to, (int)graph[to].size(), 1, 0};
        Edge revE = {from, (int)graph[from].size(), 0, 0};
        graph[from].push_back(e); // 정방향 그래프 추가 
        graph[to].push_back(revE); // 역방향 그래프 추가 
    }
}

void make_level_graph(int source, int sink) {
    // 레벨 그래프 : source -> 노드까지 최단 거리 (cap 남아 있는 경우)
    queue<int> q;
    level[source] = 0;
    q.push(source);

    while(!q.empty()) {
        int node = q.front();
        q.pop();

        // sink까지 최단 거리 계산 완료 (bfs)
        if(node == sink) break;

        // cap 남아 있고, 레벨 안 정해진 경우만 고려 
        for(auto e : graph[node]) {
            if((e.cap - e.flow) > 0 && level[e.to] == -1) {
                level[e.to] = level[node] + 1;
                q.push(e.to);
            }
        }
    }
}

int calc_blocking_flow(int node, int sink, int flow) {
    if(node == sink) return flow;

    // 현재 탐색 노드를 기준으로 blocking 안 될 때까지 dfs
    // block 안 되면 유량은 flow 중 최소값
    while(iter[node] < (int)graph[node].size()) {
        int idx = iter[node];
        Edge e = graph[node][idx];
        if((e.cap - e.flow) > 0 && level[node] < level[e.to]) {
            // cap 남아 있고, 레벨이 더 높은 곳으로 가는 경우 (레벨이 sink보다 더 뒤에 있어서 안 정해질 수도 있음)
            // 현재까지 계산된 flow와 지나갈 edge의 cap 중 최소값이 증강 경로 상 유량 
            int f = calc_blocking_flow(e.to, sink, min(flow, e.cap - e.flow));

            if(f > 0) {
                graph[node][idx].flow += f;
                graph[e.to][e.rev].flow -= f;
                return f;
            }
        }
        iter[node]++;
    }

    return 0;
}

int dinic(int source, int sink) {
    // 최대 유량 계산 
    int flow = 0;

    while(true) {
        // 레벨 그래프 초기화 
        fill(level.begin(), level.end(), -1);
        // 레벨 그래프 계산 
        make_level_graph(source, sink);
        // sink의 level 이 -1인 경우, sink까지 가는 경로 없음. 즉, 더 이상 유량 가는 경로 없음 
        if(level[sink] == -1) break;

        // iter 초기화 
        fill(iter.begin(), iter.end(), 0);
        // blocking flow 계산
        while(true) {
            int f = calc_blocking_flow(source, sink, INF);
            // 최대 유량에 추가 
            flow += f;
            // 현재 레벨 그래프에서는 더 이상 추가할 유량 없음 
            if(f == 0) break;
        } 
    }

    return flow; 
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    init();
    cout << dinic(SOURCE, SINK);
}