최대 흐름 문제 기본 개념 with 백준 6086번: 최대 유량 (Java)

개요

당연하게도, 코테를 준비하는데 있어서 네트워크 플로우는 '투머치'합니다. 코테를 준비하는데 있어서 바킹독 선생님이 다루는 범위도 과분하다고 할 정도로 충분하고(해당 문제집에는 위상 정렬, MST, 수학 등 출제 빈도가 낮은 알고리즘도 있습니다), 카카오와 같은 코테가 '빡센' 곳을 생각해도 트라이, 세그먼트 트리, KMP 정도만 추가하여 준비하는 것이 최선입니다. 그러나, 1) 최근에 본 현대모비스 알고리즘 경진대회, 그리고 네이버 코테(확실하지 않음: 시간이 없어서 문제 자체를 못 봤음...ㅠ)에 나왔으며, 2) 궁금하며 3) 솔브닥 티어좀 올리고 싶어서 흐름 네트워크에서의 최대 유량을 구하는 알고리즘을 공부, 정리하였습니다.

 

기본 개념

Everenew님 글: 대부분의 블로그 포스트가 종만북을 기반으로 개념 설명을 작성하였습니다. 그러다보니 똑같은 부분에서 이해가 안 가곤 했었는데, 이 분 글은 그보다 살짝 더 자세히 설명을 해두었으며, (친절하게 주석을 달아놓은) 코드 구현도 같이 있어 참고하기 좋습니다.

가젤님 글 (최대 흐름 문제 이해하기 / 포드-풀커슨 방법 / 에드몬드-카프 알고리즘): 설명이 매우 자세하고, 개념에 기반하여 탄탄합니다. 백준 문제 하나 풀겠다고 모든 흐름을 하나하나 다 따라갈 필요는 없어보이나, 자세하기 때문에 이해 안 되는 부분을 이해하기 좋습니다. 저는 에드몬드-카프 알고리즘의 시간복잡도가 O(VE^2)임을 이해하는데 해당 블로그 글이 매우 도움이 됐습니다. 저런 증명이 없었다면, 그냥 외워야했을 듯합니다.

구사과님 글: 사실 개념과는 큰 상관이 없으며, 제 실력에 너무 과분한 글이긴 하나, 그래도 고수분 글은 한 번 보면 재미있지 않나... 싶어서 넣었습니다.

 

개념 및 흐름

가젤님 글을, (거의 표절하여) 정리 및 증명을 생략하여 '내가 나중에 다시 봤을 때 이해할 수 있는 수준'으로 정리했습니다.

 

<개념>

간선의 용량(capacity): 각 간선마다 흐를 수 있는 최대 유량

시점(source): 흐름이 시작되는 정점

종점(sink): 흐름이 끝나는 정점

평행 간선(parallel edge): 어떤 간선에 대해, 시작점과 종점이 같은 간선

역평행 간선(anit-parallel edge): 어떤 간선에 대해, 시작점이 종점이며 종점이 시작점인 간선

잔여 네트워크(Residual Network): 현재 흐름 f에 대해, 1) '유량보다 용량이 커서 더 흐를 수 있는 간선' 및 2) '간선의 방향에 대해 역으로 흐르고 있어, 유량을 줄임으로써 현재 방향으로의 유량을 늘리는 효과를 줄 수 있는 간선'의 집합

 - 1)을 전진 간선(forward edge), 2)를 후진 간선(backward edge)라고 부른다.

증가 경로(argumented path): 현재 흐름 f에 대해, source에서 sink로 갈 수 있는 단순 경로를 찾아 전진 간선에 대해서는 경로 상 가장 작은 용량만큼 흐름을 늘려주고, 후진 간선에 대해서는 경로 상 가장 작은 용량만큼 흐름을 줄여주는 계산을 수행할 때의 경로

포드-폴커슨 방법(Ford-Fulkerson method): 현재 흐름 f에서 시점에서 종점으로 가는 임의의 단순 경로 P를 증가 경로로 하여 유량을 증가시켜, 과정을 반복하여 최대 흐름을 찾는 방법

에드몬즈-카프 알고리즘(Edmonds-Karp Algorithm): 현재 흐름 f에 대해 시점에서 종점으로 가는 단순 경로 P를 '간선의 개수가 가장 적은 경로'로 선택하여 포드-폴커슨 방법을 수행하는 알고리즘

 

<흐름>

1. 최대 유량 문제는 source에서 sink까지 가는 가장 큰 유량을 찾는 것이다.

2. 일반성을 잃지 않고, 루프는 제외해도 되며, 평행 간선은 용량을 더하여 합치면 되고, 역평행 간선은 '가상의 정점을 만들어 해당 점을 거치는 방식'으로 처리할 수 있다. 다만, 일반적인 백준 스타일 문제에서는 역평행 간선은 제거하지 않으며, 아래의 내용은 역평행 간선이 있는 데에서도 성립한다.

3. 간단한 그래프에서는 '딱 봐도' 최대 유량이 어떤지 계산이 되지만, 그래프가 조금만 복잡해져도, 어떤 경로가 올바른지 파악하기 힘들어 잘못된 경로로 지나치게 많은 유량을 보낼 수 있다. 이를 해결하기 위해, 현재 흐름 f에 대한 잔여 네트워크라는 개념을 도입하여, 특정 간선에서 유량을 흘리고 있다면, 역방향에는 -(유량)이 흐르고 있다고 하여 해당 흐름을 취소할 수 있도록 한다.

4. 현재 흐름 f가 있다면, 잔여 네트워크에서 증가 경로를 구하여 연산을 취하면 해당 연산으로 만들어진 새로운 흐름 f'에서의 유량은 f에서의 유량보다 무조건 크다(정리 및 증명은 가젤님 블로그.). 이렇기 때문에 우리는 해당 경로를 '증가' 경로라고 부르는 것이다.

5. 흐름 f에서 증가 경로를 구하여 연산을 수행하는 과정을 반복하면 최대 흐름에 도달하게 된다. 최대 흐름에 대해서, 잔여 네트워크에서 source에서 sink로 가는 단순 경로를 찾을 수 없게 된다. 해당 명제는 역도 참이게 되어, 이는 포드-폴커슨 방법의 이론적 바탕이 된다.

6. 포드-폴커슨 방법은 흐름 f에 대해, 잔여 네트워크에서 source에서 sink로 가는 임의의 단순 경로 P를 찾아 증가 경로를 구하여, source에서 sink로 가는 단순 경로를 찾을 수 없을 때까지 반복하는 방법이다. 5번에 의해, 이렇게 구한 흐름은 최대 흐름이 된다. 다만 이 방법은 '입력값의 길이(비트 개수)에 대해서 다항시간 알고리즘이 아닌' 유사 다항시간 알고리즘(Wikipedia)이라는 문제점이 있다.

7. 포드-폴커슨 방법에서 임의의 단순 경로 P를 찾을 때, P를 'source에서 sink까지의 간선의 개수가 가장 작은' 경로로 찾으면 에드먼즈-카프 알고리즘이 된다. 에드먼즈-카프 알고리즘에서, 한 간선이 '병목 간선'이 되는 경우는 최대 V/2번이며, 잔여 네트워크에서 간선은 최대 2*E개, 매 번 증가경로를 찾는 BFS는 O(E)이므로 에드먼즈-카프 알고리즘은 O(VE^2) 시간 복잡도를 가진다.

 

... 적고보니 '남이 보고 이해하는 글'은 아닌 듯합니다. 가젤님 블로그에서 그림 및 정리&증명과 같이 보는게 좋지 않을까 싶습니다.

 

구현

각 간선에서의 용량을 V*V의 이차원 배열 'capacity'로 선언하여: capacity[i][j] == '간선 i->j의 용량'으로 정의합니다.

마찬가지로, 각 간선에서의 흐름을 V*V의 이차원 배열 flow로 선언하여: flow[i][j] == '간선 i->j의 유량'으로 정의합니다.

capacity 및 flow에서 bfs를 수행할 수 있지만, 시간 복잡도가 O(V^2)가 됩니다. 따라서, BFS의 시간 복잡도를 O(E)로 수행하고자 한다면 인접 리스트를 만들어줄 필요가 있습니다.

 

에드몬즈-카프 알고리즘 구현

static int maximumFlow(int source, int sink) {
    int totalFlow = 0;
    while(true) {
        int[] parent = new int[SIZE];
        parent[source] = source;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(source);
        // BFS로 갈 수 있는, 간선의 개수가 가장 적은 경로 찾기
        while(!queue.isEmpty() && parent[sink] == 0) {
            int cur = queue.poll();
            for (int nxt: graph.get(cur)) {
                if ((capacity[cur][nxt] > flow[cur][nxt]) && parent[nxt] == 0) {
                    parent[nxt] = cur;
                    queue.offer(nxt);
                }
            }
        }
        
        // sink까지 도달할 수 없다면: 갱신할 수 없음
        if(parent[sink] == 0) {
            break;
        }
        
        // 추가로 흘려줄 유량 == 경로에서의 최소 잔여 용량.
        int temp = Integer.MAX_VALUE;
        for(int cur = sink; cur != source; cur = parent[cur]) {
            temp = Math.min(capacity[parent[cur]][cur] - flow[parent[cur]][cur], temp);
        }
        
        // 증가 경로의 전진 간선은 유량 증가, 후진 간선은 유량 감소
        for(int cur = sink; cur != source; cur = parent[cur]) {
            flow[parent[cur]][cur] += temp;
            flow[cur][parent[cur]] -= temp;
        }    
        totalFlow += temp;
    }
    return totalFlow;
}

 

---

 

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

6086번: 최대 유량

 

 

풀이

입력값에 1) 파이프의 이름이 같은 경우(==루프), 2) 같은 간선이 여러 번 등장하는 경우(==평행 간선)가 있으니, 이를 고려하여 코드를 짜야합니다.

본 문제에서는 양방향 간선인데, 특별한 처리를 해주지 않아도 괜찮습니다.

대, 소문자 알파벳을 적당히 1~52번 정점으로 변환합니다. 일반적으로는 정점을 0번부터 세어 구현하는 듯하나, 저는 그래프 문제 풀던 습관이 남아있어서 1번부터 시작하였습니다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static final int SIZE = 53;
    static int[][] flow = new int[SIZE][SIZE];
    static int[][] capacity = new int[SIZE][SIZE];
    static List<List<Integer>> graph;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        graph = new ArrayList<>();
        for(int i = 0; i < SIZE; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = toIdx(st.nextToken());
            int to = toIdx(st.nextToken());
            int capa = Integer.parseInt(st.nextToken());
            if(from == to) continue; // 루프 제거
            graph.get(from).add(to);
            graph.get(to).add(from);
            capacity[from][to] += capa; // 평행 간선이 합쳐지는 처리가 이루어짐
            capacity[to][from] += capa;
        }
        int ans = maximumFlow(1, 26);
        System.out.println(ans);
    }
    
    static int maximumFlow(int source, int sink) {
        int totalFlow = 0;
        while(true) {
            int[] parent = new int[SIZE];
            parent[source] = source;
            Queue<Integer> queue = new ArrayDeque<>();
            queue.offer(source);
            // BFS로 갈 수 있는, 간선의 개수가 가장 적은 경로 찾기
            while(!queue.isEmpty() && parent[sink] == 0) {
                int cur = queue.poll();
                for (int nxt: graph.get(cur)) {
                    if ((capacity[cur][nxt] > flow[cur][nxt]) && parent[nxt] == 0) {
                        parent[nxt] = cur;
                        queue.offer(nxt);
                    }
                }
            }
            
            // sink까지 도달할 수 없다면: 갱신할 수 없음
            if(parent[sink] == 0) {
                break;
            }
            
            // 추가로 흘려줄 유량 == 경로에서의 최소 잔여 용량.
            int temp = Integer.MAX_VALUE;
            for(int cur = sink; cur != source; cur = parent[cur]) {
                temp = Math.min(capacity[parent[cur]][cur] - flow[parent[cur]][cur], temp);
            }
            
            // 증가 경로의 전진 간선은 유량 증가, 후진 간선은 유량 감소
            for(int cur = sink; cur != source; cur = parent[cur]) {
                flow[parent[cur]][cur] += temp;
                flow[cur][parent[cur]] -= temp;
            }    
            totalFlow += temp;
        }
        return totalFlow;
    }
    
    // A~Z를 1~26, a~z를 27~52에 대응시키는 method
    static int toIdx(String input) {
        char temp = input.charAt(0);
        if(temp >= 'A' && temp <= 'Z') return temp - 'A' + 1;
        return temp - 'A' - 5;
    }
}