최대 유량(Network Flow), 에드몬즈-카프(Edmonds-Karp) 알고리즘

1. 최대 유량 문제

정점 간에 흐를 수 있는 양이 있을 때 그 최대치를 간선으로 표현하면 하나의 방향 그래프가 나온다. 두 정점 사이에 흐를 수 있는 최대 양을 용량(capacity), 두 정점 사이에 흐르고 있는 양을 유량(flow), 현재 남아있는 용량을 잔여용량(residual)이라고 한다. 예를 들어 파주에서 안양에 이르는 수도권 서부의 도로 교통용량을 대충 다음과 같이 표현할 수 있다.(실제로 이런 상황에다가 써먹지는 않는 듯 하다.)

그렇다면 이 그래프 외의 다른 연결을 전부 무시하고 모든 도로가 전부 비어있다고 가정했을 때 파주에서 안양까지 이어지는 도로 교통용량의 최대치는 얼마일까?

자유로에서 서부간선도로를 타면 파주-일산-고양-서울-안양으로 이어진다. 이 경로에 따르면 일산~고양 구간이 용량이 가장 적으므로 100의 용량을 갖는다. 비슷한 방법으로 어떤 경로를 찾아 경로 중 최소의 용량으로 통행량을 더해나가면 파주에서 안양에 이르는 교통용량의 최대치를 얻을 수 있다. 이와 같이 유량의 최대치를 구하는 문제를 "최대 유량(Network Flow)" 문제라고 하며 풀이로는 가장 기본적인 "포드-풀커슨 방법", bfs로 시간을 더 단축시킨 "에드몬즈-카프 알고리즘", 레벨 그래프로 최악의 경우를 완화시킨 "디닉 알고리즘", 이분 그래프인 경우에 활용 가능한 "홉크로프트-카프 알고리즘"등 이 알려져있다. 최대 유량 문제는 비교적 최근에 연구되고 있는 분야라 아직도 특수한 경우에서는 더 빠른 알고리즘이 등장하고 있다고 한다. 여기서는 적절히 사용할 수 있는 "에드몬즈-카프 알고리즘"을 소개해본다.

 

2. 최대 유량을 찾는 과정

이렇게 생긴 유향 그래프가 있다. 각 간선은 (현재 유량)/(총 용량)으로 표기했다. 여기서 A에서 F까지 최대로 흐를 수 있는 유량의 총 합은 얼마일까. 유량이 생성되는 A를 source라고 하고 유량이 도착할 지점인 F를 sink라고 한다.

경로를 찾는 조건은 이렇다.

1. 현재 정점과 연결되어있는 정점
2. 간선에 잔여 용량이 1이상
3. 최종적으로 sink에 도착

 

먼저 경로 ABCF를 찾을 수 있다. 이중 BC구간이 가장 작은 3의 용량을 가지고 있으므로 경로에 3의 유량을 추가한다. 그리고 경로 ABDECF를 찾을 수 있다. AB, BD, CF구간의 잔여용량이 2로 가장 작기 때문에 이 경로에 2의 유량을 추가한다. 다음으로 경로 ADEF를 찾을 수 있다. DE구간의 잔여용량이 1로 가장 작다. 경로에 1의 유량을 추가한다. 이렇게 F에는 6의 유량이 흘러오게 된다. 여기서 끝나면 참 간단한 그래프 탐색 문제로 끝난다. 하지만 B에서 D로 흘려보내는 유량을 E로 돌려보내면 DE구간에 잔여용량이 더 생기게 되고 ADEF로 1의 유량을 더 보낼 수 있게 된다. 따라서 이 그래프에서의 최대 유량은 7이다. 그렇다면 어떻게 해야 이 숨겨진 1의 유량을 찾아낼 수 있을까?

 

3. 음의 유량을 가진 가상의 간선

간략히 설명하면 "유량을 흘려보낼 때, 반대방향으로 흐르는 음의 유량을 만들어낸다."로 정리된다. A에서 B로 1의 유량이 있다면 B에서 A로 -1의 유량이 있다고 해도 말이 된다. 이 점을 이용하면 반대방향의 잔여용량을 만들어내면서 흘러왔던 유량을 다른 방향으로 돌려줄 수 있다.

방금 전 경로 ABCF를 찾았을 때 유량 3을 더해주면서 모든 간선에 반대 방향으로 -3의 유량을 만들어줬다. 실제로는 용량이 0이기 때문에 -3/0으로 표기한다. 이렇게 되면 잔여용량은 총 용량-현재 유량=0-(-3)=3이 된다. 이 곳으로 3의 유량이 흐를 수 있다는 말이다. 여기서 '이게 뭔 소리냐' 싶었는데 그냥 단순히 역류시켜버린다고 생각하면 이해하기 편하다. 이러면 유향 그래프로 주어진 의미가 없지 않나, 하고 걱정스럽지만 일단 결과적으로 문제 없으니 괜찮은 아이디어다. 아무튼 이렇게 유량의 반대 방향으로 음의 유량을 생성하면 이렇게 된다.

뭔가 난잡하지만 어쩔 수 없다. 파란색 간선이 유량의 반대로 생성된 가상의 음의 유량이다. 모두 현재 유량만큼의 잔여유량을 갖고 있는 셈이다. 여기서 새로운 경로를 탐색할 수 있다.

이렇게 경로 ADBEF를 찾을 수 있다. DB로 흐르는 음의 유량을 선택하는 것이다. 이게 도대체 무슨 의미일까.

 

4. 음의 유량이 갖는 의미

경로 ADBEF를 보면 가장 작은 잔여용량은 1이다. 따라서 발견한 경로에 1의 유량을 추가하면 이렇게 된다. (오류가 좀 있는데 BD의 유량은 1 줄어서 1/2가 되어야 한다.)

이렇게 F로 흘러오는 유량은 7이 되었다. 과정을 보면 이해가 되지 않지만 결과로 보면 AB로 5의 유량이 흘러오고 BCF로 3의 유량이 흘러 간다. 그리고 BDECF와 BECF로 각각 1의 유량이 흘러간다. ADEF로 2의 유량이 흘러가면 7의 유량이 흐르는 게 맞다. 그럼 과정을 이해해보자.

 

A에서 B로 넘어온 유량 5는 원래 C로 3, D로 2만큼 나뉘어 흐르고 있었다. 이때 ABD-로 넘어가던 유량 일부가 ABE-로 흐르면 BDE 구간의 유량을 감소시키고 ADE로 흐르는 유량을 증가시킬 수 있다.

하지만 이 과정이 탐색에서 이루어지지 않았으므로 여기서 AD의 잔여유량 1을 흘려보내주면 D에서 갈 곳이 없어지는데 음의 유량 DB를 선택하게 되면 B에서 D로 넘어오던 유량 1을 AD가 갖고 B로 넘어가게 된다. 이로써 DE로 흘러가던 원래 유량 1은 주인을 잃었다. 이걸 AD로 넘어온 유량이 차지하게 된다. 그리고 AD가 넘어가는 척 했던 음의 유량을 ABDE가 ABE로 바뀌면서 가져가게 되는 셈이다.

 

이 아이디어를 포드와 풀커슨이 함께 고안해냈고 BFS로 최악의 경우를 완화시킨 것이 바로 에드몬즈-카프 알고리즘이다.

 

5. 구현

에드몬즈-카프 알고리즘에서 구현해야 할 부분을 이정도로 나누어보았다.

0. 용량, 유량 그래프 생성
1. 유량이 흐를 수 있는 경로를 탐색(BFS)
2. 경로 내 최소 잔여용량 찾기
3. 유량 흘려보내고 sink에 흘러온 총 유량 더하기
4. 음의 유량 생성하고 1로 돌아가기
5. 탐색 결과 sink로 이어지는 경로가 없으면 더 이상 흘려보낼 수 있는 유량이 없으므로 종료

먼저 용량, 유량을 나타내는 그래프는 2차원 그래프로 나타냈다. 간선 (u,v)의 용량은 capa[u][v], 유량은 flow[u][v]다.

V = int(input()) # 정점의 수
capa = [[0]*(V+1) for _ in range(V+1)] # 용량
flow = [[0]*(V+1) for _ in range(V+1)] # 유량
# 이하 간선의 정보를 받으며 간선들의 용량을 설정

에드몬즈-카프 알고리즘에서는 유량이 흐를 수 있는 경로를 BFS로 탐색한다. source로부터 탐색을 시작해 sink에 닿는 즉시 해당 경로의 최소 잔여용량을 찾고 유량을 흘려보낸다. 1~5는 따로 구현할 수 없어서 그냥 한 방에 뚝딱했다.

while True:
    bfs = deque([1])
    visit = [0]*(V+1) # 어느 정점에서 넘어온 것인지 기록한다.
    while bfs:
        now = bfs.popleft()
        for next in range(1,V+1):
            if capa[now][next]-flow[now][next] > 0 and visit[next] == 0:
                bfs.append(next)
                visit[next] = now
                if next == V: break # sink에 닿으면 즉시 탈출
        
        if visit[V] == 0: break # sink에 닿은적이 없으므로 잔여용량이 있는 경로가 없다.
        
        residual = int(ie9) # 최소 잔여용량을 찾기 위해 큰 값을 설정한다.
        route = V           # 경로를 역추적한다.
        
        # 경로 역추적
        while route > 1:
            if residual > capa[visit[route]][route]-flow[visit[route]][route]:
                residual = capa[visit[route]][route]-flow[visit[route]][route]
            route = visit[route]
        
        # 유량 더하고 음의 유량 생성
        route = V
        while route > 1:
            flow[visit[route]][route] += residual
            flow[route][visit[route]] -= residual
            route = visit[route]

여기서 유량을 더할 때마다 residual을 다른 곳에 누적해주어야 최종적인 최대 유량을 얻을 수 있다.

 

6. 관련문제

백준 17412번: 도시 왕복하기 1

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

이 글에서 정리한 내용 그대로 갖다 써먹으면 바로 AC뜨는 문제.

 

백준 6086번: 최대 유량

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

양방향 간선이라 모든 용량을 양방향으로 동시에 만들어주어야 한다. 음의 용량은 반대 방향의 유량을 깎아먹으면 된다.