[ 개념 ] 43. 네트워크 유량(Network Flow)

> 네트워크 유량(Network Flow)

---

안녕하세요. 그래프에 대해서 1차적으로 쓸 내용 중에서는 마지막 개념에 달했습니다.

그런데 마지막 개념이기는 한데, 이 개념 한 부류를 설명하는 데 또 글을 엄청 써야 할 것 같네요.

그만큼 중요한 개념입니다. 최단 경로만큼이나... 아니 어쩌면 더...

최단 경로 알고리즘의 경우는 자료구조 수업 때 먼저 접하는 것도 있고, 최단경로가 무엇인가 하는 개념도 기초적인 편이라서 그렇게 어렵지는 않은데(알고리즘 자체는)

이번에 소개하려 하는 네트워크 유량(network flow)이란 개념은 상대적으로 생소합니다.

그래프의 간선에 거리, 시간이나 가중치, 즉 cost 대신에 용량(capacity)이라는 개념이 추가됩니다.

이제 두 정점 u, v를 잇는 간선 (u, v)가 있을 때, 정점 u에서 v 방향으로 간선의 용량 이하만큼의 유량(flow)을 흘려보낼 수 있습니다.

또한 그래프에 서로 다른 두 정점인 소스(source), 싱크(sink) 정점이 정해지고,

소스 정점에서 유량을 발생시켜서 간선들을 통해 싱크 정점에 도달시키는 것이 목표입니다.

유량을 발생시킬 수 있는 건 소스 정점 뿐이고, 그 외의 정점들은 자신이 받은 유량만큼만 다시 흘려보낼 수가 있습니다.

강의자료 예시 그래프를 하나 가져왔습니다. 보통 유량 그래프(flow network)는 방향 그래프인 경우가 많습니다. 물론, 무향 그래프일 수도 있습니다.

여기서 각 간선에 적힌 숫자는 거리라던가 가중치라던가 하는 게 아니라 용량입니다.

그리고 정점 S가 소스, 정점 T가 싱크입니다. 보통 소스와 싱크가 s, t로 많이 표현됩니다.

S에서 T로 유량 1을 하나 보내본 예시입니다. 각 간선의 p/q에서 p는 유량, q는 용량입니다.

일단 S에서 유량 1을 발생시켜서, 유량 1을 보낼 수 있을 정도로 용량이 충분히 남아있는 경로를 아무거나 찾아서 T까지 보낸 겁니다.

유량을 흘려보내는 것을 도중에 멈춰서는 안 되고, 반드시 T까지 도달해야만 유효합니다.

한 번 더 보내본 것인데, 여기서 간선 (D, T)는 두 경로에 모두 포함되어 있어서

두 번 보낸 유량이 모두 지나가고 있습니다.

한 번 더 다른 경로를 찾아봤는데 이번엔 간선의 용량이 넉넉해서 4를 한번에 보낼 수 있었습니다.

지금까지 S에서 T로 보낸 유량의 합은 1+1+4=6입니다.

이 상황에서 경로 [S, A, D, T]로 유량을 더 보낼 수 있을까요? 불가능합니다.

왜냐면 경로에 속한 간선 (D, T)에는 더이상 용량이 남아있지 않기 때문입니다.

여기서 유량 그래프에서 만족해야 하는 성질들을 짚고 넘어갑시다.

먼저, 각 간선에 흐르는 유량은 그 간선의 용량을 넘어서는 안 됩니다. 즉 f(u, v) ≤ c(u, v)입니다.

f, c는 각각 flow, capacity의 앞글자를 딴 것으로, 유량과 용량입니다. 보통 이렇게 표현합니다.

두 번째로, S와 T를 제외한 정점에서는 들어오는 유량 총합과 나가는 유량 총합이 같아야 합니다.

즉, Σf(k, u) = Σf(u, l)입니다.

S에는 유량이 발생하고, T에서는 유량이 종착하여 더 이상 나가지 않으므로 S에서 흘리는 유량의 합 또한 T로 들어가는 유량의 합과 같습니다.

즉, Σf(S, k) = Σf(k, T)입니다.

세 번째로, 간선 (u, v) 방향으로 유량이 흐르고 있다면, 역방향으로는 음의 유량이 그만큼 흐르고 있는 것으로 취급합니다.

즉, f(u, v) = -f(v, u)입니다.

위의 두 성질보다는 좀 덜 당연한데, 이 성질은 추후 최대 유량을 구해내는 알고리즘에서 유용하게 써먹습니다.

이제 유량이 뭔지, 유량 그래프가 뭔지 좀 감이 오시나요?

이렇게 보면, 이제 이 그래프는 S에서 T로 가는 최단 경로는 아니고, S에서 T로 동시에 보낼 수 있는 데이터라든가 사물이라든가의 양이 얼마나 될 것이냐를 묻는 것에 가깝습니다.

대역폭(bandwidth)의 개념과도 잘 맞아떨어지고, 그래서 네트워크라는 이름을 가졌을지도 모르지요.

그래서, 보통 이런 그래프가 주어지면 우리가 구해야 할 것은 이겁니다. 최대 유량(maximum flow).

S에서 T로 성질들을 해치지 않고 보낼 수 있는 최대 유량입니다.

아까 그 그래프의 답은 7인데, 이렇게 유량을 흘리면 됩니다.

최대 유량을 구하는 알고리즘은 정말 미친듯이 많고 시간복잡도도 다양한데, 보통 짜기 쉬울수록 시간복잡도가 안 좋긴 하지만... 아직은 가장 쉬운 버젼으로도 충분히 거의 모든 플로우 문제를 풀 수는 있습니...다...

그러나, 최근들어 상급 알고리즘들이 있어야만 제한시간 안에 풀 수 있는 문제의 출제빈도가 높아지고 있어서(특히 이벤트성 대회에서), 그런 알고리즘들을 모아서 따로 글을 하나 쓸 겁니다.

여담이지만 위키를 가보면 무려 최근, 그것도 2013년에 더 상향된 시간복잡도를 가진 최대 유량 알고리즘을 누가 개발했다고... 여튼 꽤 발전이 늦은 분야라 지금도 매우 활발하게 연구가 진행 중입니다. 지금 보면 별 것 아닌 것 같은(?) 성질들도 하나하나가 구글링 도중 2000년대 논문으로 심심찮게 걸려나옵니다.

일단, 제일 처음으로 소개해드릴 알고리즘은 기초 중의 기초인

플로우가 기초가 아닌데

포드 풀커슨 알고리즘(Ford-Fulkerson algorithm)입니다. 이 알고리즘의 동작원리는 간단합니다.

① S에서 T로 가는 증가 경로(augmenting path)를 아무거나 하나 찾는다. 이때, 증가 경로는 단순 경로이고, 경로상의 모든 간선에 아직 여유 용량(residual)이 남아있다. 즉, c(u, v) - f(u, v) > 0

② 증가 경로 중 차단 간선(blocking edge)을 찾는다. 이 간선은 경로상에서 c(u, v) - f(u, v) 값이 최소인 간선이다. 많아봐야 이만큼만 유량을 더 보낼 수 있을 것이다. 이 값을 F라 하자.

③ 경로상의 모든 간선에 F만큼의 유량을 추가한다. 즉, S에서 T로 이 경로를 따라서 F만큼의 유량을 새로 흘려보낸 것이다. 경로상의 모든 간선에 대해 f(u, v) += F

그런데 세 번째 성질을 만족시키기 위해 f(v, u) -= F 또한 행해야 한다. 역방향으로는 상응하는 음의 유량을 흘려주는 것.

위 과정을 더 이상 증가 경로가 없을 때까지 반복합니다. 증가 경로를 찾고, 찾은 경로에 대해 가능한 한 많은 유량을 흘려보내는 것의 반복입니다.

도중에 blocking edge라는 용어는 그냥 제가 대충 이름붙인 겁니다. Augmenting path라는 말은 실제로 쓰입니다.

그리고 그래프에서 원래 존재하는 간선 (u, v)가 있더라도 그 역방향 간선 (v, u)는 없는데, 거기다 음의 유량을 보내는 게 대체 무엇인지 아직은 좀 감이 안 오실 수도 있습니다.

(v, u)를 있긴 하지만 쓸모없는, 용량이 0인 간선이라고 생각하시면 됩니다. 아래의 예제에서 자세히 이게 어떻게 돌아가는지 살펴봅시다.

이런 예제 그래프가 있습니다. 여기서 포드 풀커슨 알고리즘을 시행할 겁니다.

일단 아무 증가 경로를 하나 찾습니다. [S, A, E, T]를 골랐는데요.

경로가 여러 개일 때 그 중 하나를 고르는 기준은 아무것도 없습니다.

따라서 제일 고르고 싶게 생긴 [S, A, D, T]를 일부러 안 고르는 것도 가능한데, 제가 지금 이런 경로를 고른 건 앞으로 어떤 특수한 상황을 발생시키려는 의도입니다.

여튼, 여기서 차단 간선은 (S, A)이고 그 값이 3-0=3이므로 이 경로로 3의 유량을 흘려보냅니다.

그 다음, 또다른 경로 [S, B, E, T]를 찾았는데 차단 간선 (B, E)에 걸려 2의 유량을 보낼 수 있습니다.

그 다음, 경로 [S, C, F, T]를 찾아서 차단 간선 (F, T)에 의해 유량 4를 보냅니다.

그럼 이제... 겉보기에는 증가 경로를 더 찾을 수가 없는데요.

[S, C, F, E, T] 경로를 찾아보자니 간선 (E, T)가 이미 꽉 차 있고...

그런데, 정말 이게 끝일까요?

만약 맨 처음에 경로 [S, A, D, T]로 유량 1을 흘려보내고,

그 다음 경로 [S, A, E, T]로 유량 2를 흘려보내고,

경로 [S, B, E, T]로 유량 2, 경로 [S, C, F, T]로 유량 4를 흘려보냈다면

아직 간선 (E, T)로 흐르는 유량이 4밖에 안 되기 때문에

경로 [S, C, F, E, T]로 유량 1을 추가로 흘려보낼 수 있어서 지금보다 답이 크게 나옵니다.

그럼, 처음에 경로를 잘못 택한 것 때문에 답을 잘못 구하게 되었다는 말인데...

사실, 아닙니다. 아직 이 그래프에도 증가 경로가 존재합니다.

아까 세 번째 성질에서 f(u, v) = -f(v, u)라고 했습니다.

간선 (u, v)가 존재한다면 c(u, v)가 양수고 c(v, u)는 0으로 취급한다고도 했습니다.

따라서, 그래프에서는 없는 간선이지만 가상으로는 있는, 간선 (A, E)의 역방향 간선 (E, A)를 들춰봅시다.

이 간선의 용량은 0인데, 여기로 지금 -3만큼의 유량이 흐르고 있습니다.

따라서 c(E, A) - f(E, A) = 0 - (-3) = 3 >0 이 되는데요!!

따라서 이 가상의 간선 (E, A)로 유량을 흘려보내는 게 가능해지고,

이렇게 경로 [S, C, F, E, A, D, T]를 찾는 것이 가능해지며 이때 유량 1을 추가로 흘려보낼 수 있습니다!!

간선 (E, A) 방향으로 유량이 1 흘렀기 때문에, 실제로 존재하던 간선 (A, E)로 흐르던 유량은 반대로 1 감소하는 효과가 생기는 것은 덤.

이게 도대체 무슨 일이냐...면, 이건 유량을 상쇄시키는 효과인데요.

원래 정점 A에서 E로 흘려보내던 유량 3 중에서 1을 철수해서 다른 정점인 D로 흘려보내게 되었다고 생각할 수가 있습니다. 이렇게 하면 원래 흐르던 유량에도 손실이 없습니다.

간선 (A, E) 방향으로 흐르던 유량 3 중에서 1만큼을 A로 다시 되돌려보내서 다른 경로로 흘려보내도록 유도한 것인데,

그 경로는 지금의 경우엔 마지막에 찾은 경로 [S, C, F, E, A, D, T] 중에서 정점 A 이후에 이어지는 부분 경로인 [A, D, T]가 됩니다.

이 경로는 맨 처음에 A에서 선택했던 경로 [A, E, T]와는 다른 방향의 경로이고, 이 경로를 뒤늦게 지나가도록 유량 일부를 돌려보낸 것이나 마찬가지가 된 겁니다.

또한 이번에 찾은 경로는 첫 번째로 찾은 경로에서 원래 사용하던 [E, T] 부분을 대신 사용하여 유량을 흘려보내는 것이나 마찬가지입니다. 즉, 서로 경로를 바꿔서 사용하고 있는 것.

첫 번째로 찾았던 경로 [S, A, E, T], 마지막 경로 [S, C, F, E, A, D, T]가 엇갈리면서

실제로는 처음부터 두 경로 [S, A, D, T]와 [S, C, F, E, T]로 각각 유량 1, 1을 보낸 것이나 마찬가지 상황으로 만들어놓은 것입니다.

이 두 경로는 원래의 경로들에서 간선 (A, E), (E, A) 전후의 경로를 서로 스왑한 형태죠. 그리고 서로가 간선 (A, E), (E, A)를 더 이상 사용하지 않게 되었고요.

간선 (A, E) 쪽으로 유량을 흘리다가 다시 (E, A) 쪽으로 유량을 흘려보내는 건 그냥 정점 A로 되돌아가는 것이나 마찬가지라 실제로 아무것도 안 한 것이나 마찬가지고 따라서 생략이 된 겁니다.

따라서, 이렇게 가능한 모든 경로를 찾은 채로 알고리즘이 종료되고, 최대 유량은 1+5+4(T로 들어가는 유량의 합)=10입니다.

이 알고리즘에서 증가 경로를 찾는 방법은 기본적으로 DFS인데요. DFS의 시간복잡도가 매번 O(V+E)입니다.

또한 이 문제의 답이 f이고, 모든 용량 단위가 정수라고 할 때 한 번 경로를 찾았을 때 유량이 최소 1씩은 보내지므로, 증가 경로를 찾는 루프는 최대 f번 실행됩니다.

따라서 포드 풀커슨 알고리즘의 시간복잡도는 최악의 경우 O((V+E)f)인데, 보통 V보다 E가 크므로 O(Ef)라 축약해서 씁니다. 보기에도 좋고.

여튼, 저 f라는 값 때문에 정말 최악의 경우엔 아주 어처구니없는 낭비 현상이 발생하기도 합니다.

정말 유명한 그래프입니다. 이런 형태의 그래프가 있다고 합시다.

바로 경로 [S, A, T]와 [S, B, T] 2개만 찾으면 총합 2000의 답을 찾을 수 있으나,

답을 찾기 전까진 대체 어떤 경로를 먼저 찾아야 최적인지 모르기에...

우리의 DFS가 이렇게 경로 [S, A, B, T]를 찾았고 유량 1만 흘렸다고 합시다. 네 뭐 여기까진 봐주는데...

그 다음에는 이번엔 [S, B, A, T]를 찾아서 또 유량을 1 흘립니다.

그러더니 다음엔 또 [S, A, B, T]로 1을 흘립니다.

그 다음엔 또 [S, B, A, T]로 1을... 이... 이 멍청아!!

이렇게 멍청하게 경로를 계속 찾으면 2000번 루프를 돌려야 합니다...

이 때문에 O(Ef)라는 시간복잡도가 나온 것이고요, 그나마 여기서야 E, f가 작아서 망정이지 만약...

)

네 그렇습니다. 우리는 망한 겁니다.

아무래도 더 좋은 알고리즘이 필요합니다... 그런데 그게 은근히 간단한데요.

단지 증가 경로를 DFS가 아니라 BFS로 찾아서, S에서 T로 가는 그때그때의 가장 짧은 경로를 찾아내는 방식을 사용하면 시간복잡도가 최대 O(VE^2)로 줄어듭니다!

이것이 에드몬드 카프 알고리즘(Edmonds-Karp algorithm)입니다. 보통 많이들 사용하는 건 이쪽이라고 보시면 됩니다.

- BOJ[6086] : Total Flow

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

이 문제를 풀어볼 건데요. 각 정점이 알파벳 대소문자 한 글자로 표현되므로 정점은 최대 52개고

언제나 소스는 'A', 싱크는 'Z'이며 간선 개수도 최대 700개. 또한 각 용량값도 최대 1,000.

최대 유량 알고리즘을 연습하기 딱 좋습니다.

그런데, 똑같은 간선 (a, b)가 짖궂게도 여러 개 존재할 수 있으므로 조심해야 합니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_V = 52;
const int INF = 1000000000;

// 정점 문자를 0~51 사이의 번호로 바꿔주는 간단한 함수
inline int CtoI(char c){
    if(c <= 'Z') return c - 'A';
    return c - 'a' + 26;
}

int main(){
    int N; // 간선 개수
    int c[MAX_V][MAX_V] = {0}; // c[i][j]: i에서 j로 가는 간선의 용량
    int f[MAX_V][MAX_V] = {0}; // f[i][j]: i에서 j로 현재 흐르는 유량
    vector<int> adj[MAX_V]; // 인접 리스트

    // 간선 정보 입력받기
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        char u, v;
        int w;
        scanf(" %c %c %d", &u, &v, &w);
        u = CtoI(u); v = CtoI(v);
        c[u][v] = c[v][u] += w; // 같은 간선이 여러 번 들어올 수 있으므로 +=
        adj[u].push_back(v);
        adj[v].push_back(u); // 역방향 간선도 추가해줘야 함
    }

    // total: 총 유량, S: 소스, E: 싱크
    int total = 0, S = CtoI('A'), E = CtoI('Z');
    // 증가 경로를 못 찾을 때까지 루프
    while(1){
        // 증가 경로를 BFS로 찾음
        int prev[MAX_V];
        fill(prev, prev+MAX_V, -1);
        queue<int> Q;
        Q.push(S);
        while(!Q.empty() && prev[E] == -1){
            int curr = Q.front();
            Q.pop();
            for(int next: adj[curr]){
                // c[i][j]-f[i][j] > 0: i에서 j로 유량을 흘릴 여유가 남았는가?
                // prev[next] == -1: next 정점을 아직 방문하지 않았는가?
                if(c[curr][next]-f[curr][next] > 0 && prev[next] == -1){
                    Q.push(next);
                    prev[next] = curr; // 경로를 기억하기 위해 prev 배열 사용
                    if(next == E) break; // 싱크에 도달하면 나옴
                }
            }
        }
        // 싱크로 가는 경로가 더 없으면 루프 탈출
        if(prev[E] == -1) break;

        // 경로상에서 가장 허용치가 낮은 곳을 찾음
        int flow = INF;
        for(int i=E; i!=S; i=prev[i])
            flow = min(flow, c[prev[i]][i]-f[prev[i]][i]);
        // 찾은 flow만큼 해당 경로에 유량 흘려줌
        for(int i=E; i!=S; i=prev[i]){
            f[prev[i]][i] += flow;
            f[i][prev[i]] -= flow;
        }
        // 총 유량 값 증가
        total += flow;
    }
    // 결과 출력
    printf("%d\n", total);
}

코드가... 길죠. 하지만 큰 구조만 파악하시면 몇 번의 연습에 걸쳐 외우실 수 있을 겁니다.

큰 구조는 아까 말씀드렸듯이 매번 가능한 증가 경로를 찾고, 찾으면 가능한 만큼 유량을 흘려보내는 겁니다.

이때 증가 경로는 BFS로 찾습니다.

용량과 유량 값을 배열로 사용해도 좋은데, V 값이 너무 크면 O(V^2)의 공간이 부족할 수도 있습니다. 그때는 어쩔 수 없이 간선을 필요한 만큼만 만들어서 써야 합니다.

초반에 가장 많이 하게 되는 실수는 역방향 간선을 추가하지 않는 겁니다.

간선 (u, v)가 들어오면 반드시 v 쪽에서도 인접리스트에 u를 넣어서 역방향 간선을 만들어 주세요!

(이 문제에서는 간선이 양방향이기 때문에 그러기가 힘들지만)

대부분의 문제 예제가 간단한 편이라 이걸 안 해도 답이 나오는 경우가 많았어요... 경험담 ㅠㅠ

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_V = 52;
const int INF = 1000000000;

// 간선 구조체
struct Edge{
    int to, c, f;
    Edge *dual; // 자신의 역방향 간선을 가리키는 포인터
    Edge(): Edge(-1, 0){}
    Edge(int to1, int c1): to(to1), c(c1), f(0), dual(nullptr){}
    int spare(){
        return c - f;
    }
    void addFlow(int f1){ // 자신과 역방향 간선에 f1만큼의 플로우 값을 갱신
        f += f1;
        dual->f -= f1;
    }
};

inline int CtoI(char c){
    if(c <= 'Z') return c - 'A';
    return c - 'a' + 26;
}

int main(){
    int N;
    vector<Edge*> adj[MAX_V]; // 존재하는 간선만을 인접 리스트로 저장
    // 간선 정보 입력받음
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        char u, v;
        int w;
        scanf(" %c %c %d", &u, &v, &w);
        u = CtoI(u); v = CtoI(v);
        Edge *e1 = new Edge(v, w), *e2 = new Edge(u, 0);
        e1->dual = e2;
        e2->dual = e1;
        adj[u].push_back(e1);
        adj[v].push_back(e2);
    }

    int total = 0, S = CtoI('A'), E = CtoI('Z');
    while(1){
        int prev[MAX_V];
        Edge *path[MAX_V] = {0}; // 경로상의 간선들을 저장해두어 나중에 참조
        fill(prev, prev+MAX_V, -1);
        queue<int> Q;
        Q.push(S);
        while(!Q.empty() && prev[E] == -1){
            int curr = Q.front();
            Q.pop();
            for(Edge *e: adj[curr]){
                int next = e->to;
                if(e->spare() > 0 && prev[next] == -1){
                    Q.push(next);
                    prev[next] = curr;
                    path[next] = e;
                    if(next == E) break;
                }
            }
        }
        if(prev[E] == -1) break;

        int flow = INF;
        for(int i=E; i!=S; i=prev[i])
            flow = min(flow, path[i]->spare());
        for(int i=E; i!=S; i=prev[i])
            path[i]->addFlow(flow);
        total += flow;
    }
    printf("%d\n", total);
}

이것이 필요한 간선만을 구조체로 정의해서 저장하는 코드인데요.

이걸 구현하는 방법은 굉장히 많은데 가장 골치 아픈 건 역방향 간선을 가능한 한 빠르게 참조하는 겁니다.

제가 선호하는 방식은 처음부터 간선을 두 방향 모두 만들어서 서로를 가리키고 있게 만드는 것으로, dual 포인터가 그 역할을 하고 있습니다.

방향이 없는 그래프에서도 최대 유량을 찾는 건 가능합니다.

간선 (u, v)에 방향은 없지만, u에서 v로만 유량을 흘리거나 v에서 u로만 유량을 흘리는 게 가능한데요.

이건 놀랍게도 그냥 양쪽 용량을 같은 값으로 초기화해 두기만 하면 구현이 됩니다. 유량을 역방향에는 빼 주는 건 똑같이 해야 합니다.

무려 이 내용을 서술한 논문도 존재합니다...

그럼 이 어마무시한 플로우라는 개념을 활용할 수 있는 문제를 몇 개만 살펴봅시다.

- BOJ[2188] : 축사배정

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

이 문제를 보면, 축사 하나엔 소 한 마리만 들어갈 수 있는데, 여기다 각 소는 들어갈 수 있는 축사의 번호들이 한정되어 있습니다.

이때, 소와 축사를 각각 정점으로 만들고 소 정점 A에서 축사 정점 B로 유량 1을 흘려보내면, 소 A가 축사 B에 들어가는 것과 같은 효과를 낼 수 있습니다.

또한 각 소는 하나의 축사에만 들어갈 수 있고, 각 축사에도 한 마리의 소까지만 들어갈 수 있다는 점을 용량으로 잘 해결하면 다음과 같은 그래프가 모델링됩니다.

예제에서 소 정점을 순서대로 A

E, 축사 정점을 1

5라고 하고

S에서 각 소 정점으로 갈 수 있고, 각 축사 정점에서 T로 갈 수 있다고 하며

각 소마다 들어가도 괜찮은 축사로만 간선을 연결해 주고, 모든 간선의 용량을 1이라 합시다.

여기서 다음과 같이 유량 1을 보낸다는 것은, 소 A가 2번 축사에 들어간다는 의미입니다!

또한 S에서 어떤 소로 가는 용량이 1이으모 소 A가 다른 축사에 한 번 더 동시에 들어가는 것은 불가능합니다. 즉, 소 한 마리는 축사 하나에만 들어간다는 조건을 지킵니다.

그리고 축사에서 T로 흐르는 유량도 최대 1이라는 점이, 축사 하나엔 최대 소 한 마리만 들어갈 수 있다는 조건을 지키게 해 줍니다.

이렇게 치면, 사실 가운데의 간선 용량들은 1 이상의 어떤 값이어도 상관없게 됩니다.

따라서 이 그래프에서 S에서 T로 유량을 1 흘려보내는 게 소 한 마리를 어떤 축사로 들인다는 의미이며, 흘려보낼 수 있는 최대 유량이 답이 됩니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_V = 800;

struct Edge{
    int to, c, f;
    Edge *dual;
    Edge(): Edge(-1, 0){}
    Edge(int to1, int c1): to(to1), c(c1), f(0), dual(nullptr){}
    int spare(){
        return c - f;
    }
    void addFlow(int f1){
        f += f1;
        dual->f -= f1;
    }
};

int main(){
    // 각 정점 n은 두 개의 정점 n*2-2, n*2-1로 나뉘어진다.
    int N, P;
    vector<Edge*> adj[MAX_V];
    scanf("%d %d", &N, &P);
    // 각 정점을 분리하고 사이에 용량 1인 간선 추가
    for(int i=0; i<N; i++){
        int u = i*2, v = u+1;
        Edge *e1 = new Edge(v, 1), *e2 = new Edge(u, 0);
        e1->dual = e2;
        e2->dual = e1;
        adj[u].push_back(e1);
        adj[v].push_back(e2);
    }
    // 간선을 입력받아 분리된 정점에 맞게 방향 간선 2개 추가
    for(int i=0; i<P; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        // 순방향 간선 (나가는 정점 -> 들어가는 정점)
        Edge *e1 = new Edge(b*2, 1), *e2 = new Edge(a*2, 1);
        e1->dual = e2;
        e2->dual = e1;
        adj[a*2+1].push_back(e1);
        adj[b*2+1].push_back(e2);
        // 역방향 간선
        e1 = new Edge(a*2, 1); e2 = new Edge(b*2+1, 0);
        e1->dual = e2;
        e2->dual = e1;
        adj[b*2+1].push_back(e1);
        adj[a*2].push_back(e2);
    }

    // 최대 유량 구하기
    int total = 0, S = 1, E = 2;
    while(1){
        ...
    }
    // 결과 출력
    printf("%d\n", total);
}

에드몬드 카프 알고리즘으로 푸는 소스 코드입니다.

어때요, 최단 경로 알고리즘 때와는 다르게, 원래는 이게 유량을 흘리는 문제인가 하는 느낌이 잘 안 옵니다. 아니 소가 유량이라니요...

적절하고 영리한 모델링을 거쳐서 뜬금없이 플로우 그래프로 바꾸어야만 합니다...

플로우 챕터의 진입장벽이 좀 높은 이유. 척 보고 여기서 플로우를 발상하는 게 쉽지는 않습니다.

또한, 이 문제의 경우 수많은 유량 그래프 중에서도 좀 특이한 형태인데, 이런 형태의 그래프에 대해서 더 빠르게 최대 유량을 구하는 방법이 있고 이건 다음 글에 포스팅하겠습니다.

- BOJ[17412] : 도시 왕복하기 1

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

이 문제는, 단방향 그래프이고 각 간선을 한 번씩만 써서 1, 2번 도시를 최대 왔다갔다할 수 있는 횟수를 구하라네요. 도대체 이게 뭐냐...

여기서 한 가지 팁을 드리자면, 플로우 그래프의 가장 큰 특징은 바로 간선의 용량입니다.

어떤 길을 한 번만 지날 수 있다는 말은, 그 간선의 용량이 1이라는 것과 동치입니다.

또한, 1->2->1->2... 식으로 왔다갔다하는 경로는, 바꿔 말하자면 1번 정점에서 2번 정점으로 경로가 하나도 겹치지 않게 하면서 갈 수 있는 서로 다른 경로의 개수입니다.

그렇습니다. 이건... 1번을 소스, 2번을 싱크로 하는 플로우 그래프이며 여기서 최대 유량이 답입니다.

왼쪽이 예제 그래프이고 오른쪽이 정답의 경우입니다. 총 2개의 경로가 존재하고 이건 최대 유량이 2였다는 겁니다.

- BOJ[2316] : 도시 왕복하기 2

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

그런데 좀 더 발전한 문제가 있습니다. 여기서는 간선의 방향도 양방향으로 바뀐 것에 더해, 또 하나 고려해야 할 것이 있습니다. 각 정점도 한 번만 지날 수 있다는 겁니다.

앞서 본 문제의 예제의 경우 다행히도 그냥 경로 두 개 찾았더니 이 조건도 만족했지만,

이런 형태의 그래프라면 답은 1인데, 간선 용량만 1로 둬서는 최대 유량이 2라고 판단해버립니다.

정점을 한 번만 지날 수 있다는 조건은 어떻게 구현할 수 있을까요?

그것은 정점 하나를 2개의 정점으로 나눠서, 그 사이의 간선 용량을 1로 지정해버리는 겁니다.

각 정점이 이렇게 세포분열(?)을 해서, 하나는 들어오는 방향의 정점이고 하나는 나가는 방향의 정점이 되었습니다. 원래 정점 u에 대해 이들을 각각 u, u'라 칭한다면,

원래 양방향 간선 (u, v)가 있었다면 (u', v)와 (v', u) 이렇게 2개의 간선으로 분리시켜 주는 것입니다.

또한 (u, u') 간선도 추가시켜 주는데 이 간선의 용량이 반드시 1이어야 합니다. 이것이 이 u라는 정점을 한 번만 지날 수 있게 해 주는 역할을 합니다.

지금 추가되는 간선은 모두다 방향 간선입니다! 주의하세요.

또한, 시작점과 도착점에 한해서는 시작점으로 들어오는 간선이나 도착점에서 나가는 간선은 안 만들어도 됩니다. 만들어도 되지만요.

이 상태에서 최대 유량을 찾으면 중간의 (4, 4')를 항상 지나야 해서 1이 나옵니다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_V = 800;

struct Edge{
    int to, c, f;
    Edge *dual;
    Edge(): Edge(-1, 0){}
    Edge(int to1, int c1): to(to1), c(c1), f(0), dual(nullptr){}
    int spare(){
        return c - f;
    }
    void addFlow(int f1){
        f += f1;
        dual->f -= f1;
    }
};

int main(){
    // 각 정점 n은 두 개의 정점 n*2-2, n*2-1로 나뉘어진다.
    int N, P;
    vector<Edge*> adj[MAX_V];
    scanf("%d %d", &N, &P);
    // 각 정점을 분리하고 사이에 용량 1인 간선 추가
    for(int i=0; i<N; i++){
        int u = i*2, v = u+1;
        Edge *e1 = new Edge(v, 1), *e2 = new Edge(u, 0);
        e1->dual = e2;
        e2->dual = e1;
        adj[u].push_back(e1);
        adj[v].push_back(e2);
    }
    // 간선을 입력받아 분리된 정점에 맞게 방향 간선 2개 추가
    for(int i=0; i<P; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        Edge *e1 = new Edge(b*2, 1), *e2 = new Edge(a*2, 1);
        e1->dual = e2;
        e2->dual = e1;
        adj[a*2+1].push_back(e1);
        adj[b*2+1].push_back(e2);
    }

    // 최대 유량 구하기
    int total = 0, S = 1, E = 2;
    while(1){
        ...
    }
    // 결과 출력
    printf("%d\n", total);
}

소스 코드입니다.

정점 개수가 최대 800개이기 때문에, 2차원 배열로 c, f를 만들기에 무리가 있을 수 있습니다.

- BOJ[5651] : Crucial Links

이 문제는 유량 그래프에서, 용량이 줄어들면 최대유량도 줄어들게 되는 간선을 crucial link라 칭하고, 그러한 간선이 몇 개나 되는지를 찾으라는데요.

대체 이딴 걸 어떻게 풀까... 그런데 이 문제에서 은근히 친절한 제약이 많습니다. 총 용량 합이 20,000을 넘지 않는다던가...

일단 최대유량을 구하는 건 에드몬드 카프로 풀더라도, 시간복잡도는 O(VE^2)가 아니라 포드 풀커슨의 것이었던 O(Ef)가 됩니다. 네. 둘 중 작은 쪽이 시간복잡도가 되는 겁니다. 에드몬드 카프가 단순히 포드 풀커슨에서 경로만 빨리 찾는 변형이니까, 원래의 시간복잡도 O(Ef)보다는 나쁠 리가 없죠.

일단 최대유량을 찾은 후, 마지막 상태의 그래프에서 포화 간선을 찾습니다. 이건 가능한 한 많은 유량이 흐르고 있는, 즉 c[u][v] = f[u][v]인 간선 (u, v)를 말합니다.

그리고 각 포화 간선 (u, v)마다 용량을 1 줄여 보고, 그때 정점 u에서 다른 경로로 우회해서 v로 유량 1을 더 보낼 수 있는지 판단해 봅니다. 지금까지처럼 그냥 경로를 찾기만 하면 됩니다.

찾으면 그건 crucial link가 아니고, 못 찾으면 crucial link가 맞습니다. 이런 식으로 개수를 세면 됩니다.

- BOJ[11495] : 격자 0 만들기

이 문제는 좀 어렵습니다. 그런데 이렇게 격자판 형태의 뭔가가 주어지면, 정점들을 체크판 무늬에 따라 양분해보는 아이디어를 시도할 수 있습니다.

두 번째 예제에서 각 칸을 정점이라 하면 이렇게 양분할 수가 있는 겁니다.

이제 뭘 할까요? 일단 하는 연산이 인접한 두 칸을 고르는 것이므로, 여기서 항상 파란색 정점 하나, 빨간색 정점 하나를 고르는 꼴이 됩니다.

문제에서는 최소 연산 횟수를 구하라고 했고 이건 우리가 지금까지 구해온 최댓값과는 반대의 방향인데요.

근데 일단 그걸 무시하고, 인접한 정점 2개를 골랐을 때 둘 다 1 이상인 한 최대 몇 번까지 연산을 할 수 있는지를 구해봅시다. 그것은...

이렇게 표현할 수 있습니다. 아까 축사 배정 문제와 비슷한데, 이번엔 S, T와 이어진 간선 용량이 꼭 1은 아닙니다.

네. 그 용량은 바로, 반대편 정점의 위치에 적힌 값입니다!

그리고 가운데의 간선은 서로 인접할 때만 존재합니다. 각 정점의 두 값은 x, y좌표를 의미합니다. 열 번호, 행 번호 순입니다.

여기서 이런 경로로 유량을 1 보냈다는 말은?

좌표 (0, 0)과 (0, 1)을 묶어서 한 번 연산을 했다는 말입니다. 즉, 유량 1 당 한 번의 연산입니다.

지금 구하려는 게, 연산을 할 때 둘 다 값이 1 이상 남아있어야 하는 것이므로 양쪽 정점과 S, T 사이에 여유가 있어야 하고 이건 맞습니다.

그럼 이 그래프에서 최대 유량을 구하면 그게 일단 답은 아니겠죠. 여기서 뭘 할 수 있을까요?

이런 식으로 유량을 흘려보내면서 그에 맞게 값을 감소시켜 갔다면, 격자판에 남아있는 0 초과의 값들은 절대 서로 인접하지 않은 상태일 겁니다.

따라서 이 남은 값들은 반드시 1 감소시키는 데 한 번의 연산을 해 줘야겠죠.

그렇습니다. 답은... 위 그래프의 최대 유량 + 남은 값들의 합입니다.

최대 유량을 구한 행위가 쓸데없이 낭비하는 연산을 없게 하고 최대한 효율적으로 값들을 지워나갔을 때 몇 번의 연산이 필요한지를 구한 것이나 다름없어서, 그 횟수와 남은 수들을 처리하는 연산 횟수를 더하면 답이 되는 겁니다.

이 식을 변형하면, 원래 격자판에 있던 값들의 총합을 S라 하고 최대 유량을 F라 할 때 남은 값들의 합이 S-2_F이므로, F + S-2_F = S - F 또한 답이 됩니다.

어마무시하죠.

사실 플로우를 처음 배우고 응용문제를 푸는 건 정말 대단히 어렵고 불가능에 가까운 일입니다. 연습을 꽤 여러 번 하거나, 여러 번 공부하는 수밖에 없습니다.

저도 응용문제를 그나마 많이 풀게 되는 데 한 3번의 시도가 필요했고, 유명한 플로우 문제들은 구글링하면 풀이가 많이 나오므로 검색을 적극 활용합시다.

그나마 이게 플로우 문제일 확률이 높다는 단서를 던져주는 조건으로는 이런 게 있습니다.

"동시에 n명만 지날 수 있다", "n번까지만 쓸 수 있다"

일단, 대부분의 문제들은 최대한 단순히 생각해 봅시다. 정점이 좀 많아진다고 느껴도 의외로 빠른 시간 안에 답이 찾아질 수 있기 때문. 아래의 문제 중 상당수가 그러합니다.

물론 시간 초과가 나게 되는 문제들은 추후 업로드할 다른 알고리즘들을 사용해야겠지만요. 다행히 아직은 그런 문제가 많지는 않습니다. (올해 전대프연에 그런 문제가 2개나 나온 건 신경쓰지 맙시다.)

네트워크 유량 관련 문제

6086번: Total Flow

위에서 설명한 문제입니다.

2188번: 축사 배정

위에서 설명한 문제입니다.

17412번: 도시 왕복하기

위에서 설명한 문제입니다.

2316번: 도시 왕복하기 2 (★)

위에서 설명한 문제입니다.

7616번: 교실로 가는 길 (★)

도시 왕복하기 문제와 유사한데, 역시 이번에도 정점이건 간선이건 하나도 안 겹쳐야 합니다.

게다가 이번엔 최대 유량을 구하는 게 아니라, K개의 경로가 존재하느냐, 즉 유량 K를 보낼 수 있느냐를 묻는 문제입니다. 가능한지 불가능한지 직접 돌려보고 판단하면 됩니다.

그런데 그것도 모자라서, 가능하면 그때의 경로를 다 출력하라네요. 이건 유량을 흘려보낸 것과 반대로 할 수 있습니다.

소스에서 싱크로 유량이 흐르는 중인 어떤 경로를 찾고, 이 경로를 정점 번호가 중복되지 않게 잘 출력하면서 경로상의 유량을 다 없앱니다. 이걸 K번 반복하면 됩니다.

5651번: Crucial Links (★)

위에서 설명한 문제입니다.

1658번: 돼지 잡기

문제가 상당히 복잡한데, 각 날짜마다 손님의 정점과 모든 돼지우리의 정점을 싸그리 다 만들어서 O(MN)개 정점을 만들어 최대 유량을 구하면 됩니다. 정점 개수가 꽤 많은데도 시간 안에 잘 풀립니다.

예제에 해당하는 그래프입니다. 생각해보니 초기 우리에 대한 정점은 없어도 되겠네요.

여튼 이 그래프에서 유량 1을 소스에서 싱크로 흘려보내는 것이 돼지를 누군가에게 한 마리 파는 것과 같습니다. 값이 없는 간선의 용량은 다 ∞입니다.

소스에서 1일차의 돼지우리들로 초기에 있던 돼지 마릿수만큼 용량을 설정해주고, 각 손님 정점에서도 최대 살 수 있는 돼지 마릿수만큼의 용량을 갖고 싱크로 간선을 만들어 줍니다.

그리고 각 손님마다 원하는 돼지우리에서 올 수 있도록 간선을 만들고, 해당 돼지우리들끼리는 추가로 돼지를 재배치할 수 있도록 다음 날짜에 다른 우리로 가는 간선을 가능한 한 다 만들어주고...

지독한 그래프네요.

11495번: 격자 0 만들기 (★)

위에서 설명한 문제입니다.

10319번: Avoiding the Apocalypse (★)

일단 의료시설에서 모두 별도의 싱크 정점으로 향하는 간선을 만들어주고, 소스에서는 i번 정점으로 용량 g의 간선을 만들어주면 될 것 같은데...

간선마다 한 번에 통과할 수 있는 사람 수야 용량이라는 걸 쉽게 알 수 있지만, 문제는 지나는 시간.

이걸 구현하는 방법은 생각보다 쉽고 단순합니다. 각 정점을 시간 정보로 쪼개는 것.

즉, 정점 u가 현재 시간 정보까지 포함하여 (u, 0), (u, 1), (u, 2), ... 등으로 쪼개어지는 겁니다.

간선 (u, v)가 용량 p를 갖고 있고 통과하는 데 시간 t가 걸린다고 할 때, 임의의 가능한 0 이상의 모든 시간 k에 대해서 정점 (u, k)와 정점 (v, k+t)를 용량 p로 이어주면 됩니다.

또한 그자리에서 머무는 것도 가능하므로, 정점 (u, k)에서 정점 (u, k+1)로 용량 ∞의 간선도 만들어줍니다.

이렇게 그래프를 모델링하면 미친듯이 많은 개수의 정점이 생길 테니, 일단은 처음에 주어지는 시간제한 s를 잘 활용하여 각 정점마다 0~s, 즉 s+1개 정점으로만 쪼개주면 총 정점은 O(sn)개가 됩니다. 간선은 O(sr)개가 되겠네요.

거기다 최대 유량은 당연히 g니까, 이 문제의 시간복잡도는 O(srg)입니다. 100_1000_100 = 10^7. 놀랍게도 충분한 시간입니다;

3666번: 리스크 (★)

문제 해설이 모호할 수 있는데, 목표는 한 턴이 지난 후 적진과 인접한 모든 아군의 진영들 중 각각 주둔한 군대의 수 중 최솟값을 최대가 되게 하는 겁니다.

즉, 두 번째 예제에서 답이 4라는 것은 적진과 인접한 3, 4, 7번 진영 모두에 한 턴 이후 최소 4명씩 주둔시킬 수 있다는 말입니다. 물론, 다른 진영에도 1명 이상은 있어야 합니다.

이분 탐색입니다. 인접 지역에 각각 k명을 주둔시키는 것이 가능한지 판별하며, 최대의 k를 찾아야 합니다.

k명을 주둔시키는 게 가능한지를 판별하는 유량 그래프는 다음과 같습니다.

정점 u, u'으로 나누어지는데, u'은 한 턴이 지난 후의 정점이라 보시면 됩니다.

간선 (S, u)는 원래 지역 u에 있던 군대 수, 간선 (u', T)는 u'가 적진과 인접해있지 않으면 1이고(최소 한 명은 남아있어야 하므로) 인접해있으면 k입니다.

그리고 두 지역 u, v가 인접해있으면 간선 (u, v'), (v, u')를 추가해 줍시다. 용량은 ∞.

여기서 T로 들어가는 모든 간선이 포화가 되게 유량을 흘릴 수 있으면 가능합니다.

이 그래프에서 유량이 의미하는 바는 원래 있던 군대를 다른 인접한 곳으로 이동시키는 것과 같겠습니다.

참조
https://blog.naver.com/kks227