Maximum Flow Ford Fulkerson Python Implementation, 최대 유량 포드 풀커슨 파이썬 구현 (Feat. Google Foo Bar Challenge Level 4)

Maximum Flow

어떤 그래프 G = (V, E)에 대해, 간선 E에 최대로 흐를 수 있는 capacity가 주어질 때, source s에서 sink t로 흐를 수 있는 최대 유량을 묻는 문제다.

Introduction To Algorithms, Third Edition

Ford Fulkerson 알고리즘

최대 유량 문제를 해결할 수 있는 알고리즘으로, source에서 sink로 dfs를 반복적으로 수행한다.

dfs의 결과 source에서 sink로의 flow를 추가적으로 더할 수 있으면 flow 상태를 업데이트한다.

간선 e: (u, v)가 있다면 반대쪽 간선인 (v, u)를 만드는 것도 핵심적이다.

 

Introduction To Algorithms, Third Edition

시간 복잡도는 O((V+E)*|C|), 이때 C는 가능한 최대 flow다.

dfs가 O(V+E)만큼 소요되고, 한 번에 1씩 flow가 늘어난다면 dfs를 C번 해야 할 수 있다.

 

 

그러면 아래 문제를 보자. 구글 Foo Bar Challenge 레벨 4에 나온 문제이다.

 

Escape Pods
===========

You've blown up the LAMBCHOP doomsday device and relieved the bunnies of their work duries -- and now you need to escape from the space station as quickly and as orderly as possible! The bunnies have all gathered in various locations throughout the station, and need to make their way towards the seemingly endless amount of escape pods positioned in other parts of the station. You need to get the numerous bunnies through the various rooms to the escape pods. Unfortunately, the corridors between the rooms can only fit so many bunnies at a time. What's more, many of the corridors were resized to accommodate the LAMBCHOP, so they vary in how many bunnies can move through them at a time. 

Given the starting room numbers of the groups of bunnies, the room numbers of the escape pods, and how many bunnies can fit through at a time in each direction of every corridor in between, figure out how many bunnies can safely make it to the escape pods at a time at peak.

Write a function solution(entrances, exits, path) that takes an array of integers denoting where the groups of gathered bunnies are, an array of integers denoting where the escape pods are located, and an array of an array of integers of the corridors, returning the total number of bunnies that can get through at each time step as an int. The entrances and exits are disjoint and thus will never overlap. The path element path[A][B] = C describes that the corridor going from A to B can fit C bunnies at each time step.  There are at most 50 rooms connected by the corridors and at most 2000000 bunnies that will fit at a time.

For example, if you have:
entrances = [0, 1]
exits = [4, 5]
path = [
  [0, 0, 4, 6, 0, 0],  # Room 0: Bunnies
  [0, 0, 5, 2, 0, 0],  # Room 1: Bunnies
  [0, 0, 0, 0, 4, 4],  # Room 2: Intermediate room
  [0, 0, 0, 0, 6, 6],  # Room 3: Intermediate room
  [0, 0, 0, 0, 0, 0],  # Room 4: Escape pods
  [0, 0, 0, 0, 0, 0],  # Room 5: Escape pods
]

Then in each time step, the following might happen:
0 sends 4/4 bunnies to 2 and 6/6 bunnies to 3
1 sends 4/5 bunnies to 2 and 2/2 bunnies to 3
2 sends 4/4 bunnies to 4 and 4/4 bunnies to 5
3 sends 4/6 bunnies to 4 and 4/6 bunnies to 5

So, in total, 16 bunnies could make it to the escape pods at 4 and 5 at each time step.  (Note that in this example, room 3 could have sent any variation of 8 bunnies to 4 and 5, such as 2/6 and 6/6, but the final solution remains the same.)

-- Python cases --
Input:
solution.solution([0], [3], [[0, 7, 0, 0], [0, 0, 6, 0], [0, 0, 0, 8], [9, 0, 0, 0]])
Output:
    6

Input:
solution.solution([0, 1], [4, 5], [[0, 0, 4, 6, 0, 0], [0, 0, 5, 2, 0, 0], [0, 0, 0, 0, 4, 4], [0, 0, 0, 0, 6, 6], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]])
Output:
    16

 

풀이 (Ford Fulkerson)

INF = 2000000

def _augment(path, exits, flow, u, val, visited):
    visited[u] = True
    if u in exits:
        return val
        
    n = len(path)
    for v in range(n):
        cuv = path[u][v]
        if not visited[v] and cuv > flow[u][v]:
            res = min(val, cuv - flow[u][v])
            delta = _augment(path, exits, flow, v, res, visited)
            if delta > 0:
                flow[u][v] += delta
                flow[v][u] -= delta
                return delta

def ford_fulkerson(path, exits, start):
    n = len(path)
    flow = [[0] * n for _ in range(n)]
    while _augment(path, exits, flow, start, INF, [False] * n) > 0:
        pass
    return flow, sum(flow[start])

def solution(entrances, exits, path):
    for corridors in path:
        corridors.append(0)
    path.append([INF if i in entrances else 0 for i in range(len(path[0]))])
    
    return ford_fulkerson(path, exits, len(path)-1)

Competitive Programming in Python 책을 참고하여 작성해 보았다.

 

여기서 시간 복잡도를 고려하면 C=2000000, V = 50이라 아슬아슬하다.

(다른 플랫폼이면 TLE가 떠서 실패했을 법한데, verify가 통과하여 그대로 제출했다. 이게 맞나?)

 

Doubling Flow Algorithm

Maximum Flow 문제를 O((V+E) log C)O((V+E)^2 log C)에 해결하는 기법도 있다.

Ford Fulkerson과 비슷한데, 한 번에 흘리는 유량을 2의 n승이 되게 하는 것이다.

dfs로 흘리는 유량을 delta라 하자. 이 delta는 C 이하인 2의 거듭제곱의 최댓값이다.

dfs로 흘릴 수 있는 최대 유량이 delta보다 작다면 delta를 2로 나누고, delta가 1이 될 때까지 반복한다.

 

구현은 Ford Fulkerson과 크게 다르지 않으므로 따로 하진 않지만, 나중에 필요하면 구현해서 공유하도록 하겠다.