Network Flow (최대 유량 알고리즘) 파이썬

Network Flow

최대 유량 알고리즘은 어떤 경로가 있을 때, 시작점에서 도착점까지 흐를 수 있는 최대 유량을 구하는 알고리즘이다. BFS가 단순히 최단 경로를 찾는 알고리즘이었다고 하면, 최대 유량 알고리즘은 최단 경로가 아닌 최대 유량을 구해서 더 복잡하다. 

 

Network Flow의 기본 용어

다른 블로거 분들의 내용을 참고해서, 내가 이해하기 쉬운 방법으로 간단히 정리를 해봤다. 

Network Flow에서 기본적으로 사용하는 용어는 f / c이다. 여기서 f는 flow의 약자이며, A → B로 실제로 흐르는 유량을 의미한다. c는 capacity의 약자이며, A → B로 흐를 수 있는 최대 유량을 의미한다. 즉, c와 f는 항상 c>=f를 만족해야한다. 

한 가지 더 알아야 할 개념은 A → B로 2만큼의 유량이 흐른다면, B → A로 -2만큼의 유량이 흐른다는 것을 알아야 한다. -2라는 숫자를 보면 알 수 있듯이 실제로 유량이 흐른다는 것은 아니다. 개념적인 유량인데, B → A의 유량의 숫자는 A → B만큼 흐르는 유량을 다시 뒤로 흘릴 수 있다는 것을 의미한다고 생각한다. 

 

예를 들어 A → B로 2만큼 현재는 흐르는데, 추후 알고리즘으로 최대 유량을 도출하는 과정에서 A → B에 1만큼 흘러야 하는 경우가 있다. 이 때, B → A경로를 확인했을 때 -2만큼 흐르는 것을 확인했으니 이 음수값만큼 A → B로 흐르는 유량을 거둘 수 있다. 그래서 A → B로 0만큼 흐른다고 할 수도 있고, A → B만큼 1만큼 흐를 수도 있다고 하는 것이다. 아래 예시에서 좀 더 자세히 알아볼 수 있다. 

 

 

Network Flow, DFS로 확인하기

특정 점과 점 사이에 흐를 수 있는 최대 유량을 DFS로 구할 수 있다. 아래와 같은 의사코드를 반복할 수 있는만큼 반복하면 된다. 

1. 시작점에서 도착적으로 이동할 수 있는 경로를 찾는다. (Capacity[here][next] - Flow[here][next] > 0을 모두 만족하는 경로) 
2. DFS 탐색 과정에서 "Capacity[here][next] - Flow[here][next]"의 최소값을 기록한다. 
3. 경로의 순방향 간선에는 2번에서 구한 최소값을 모두 더하고, 역방향 간선에는 2번에서 구한 최소값을 모두 뺀다.

1번 의사코드는 현재 두 점을 잇는 노드 사이에 유량이 흐를 수 있는지를 확인하는 과정이다. 간선 자체가 가질 수 있는 최대 유량보다 현재 간선에 흐르는 유량이 작을 때만 유량이 흐를 수 있기 때문이다. 그렇지만 이것은 반드시 시작점에서 도착점까지 흘렀을 때만 의미가 있다. 그렇지 않으면 유량이 이 경로로는 흐를 수 없기 때문이다. 

2번 의사코드는 전체 경로에 흐를 수 있는 최대 유량을 구하는 것이다. 예를 들어 A → B로 2, B → C로 10이 흐른다고 하면 A → B로 흐를 수 있는 최대 유량은 2이다. 이것을 구현하는 것이다.

3번 의사코드는 실제 유량을 흘려주는 것이다. 순방향으로는 실제 유량을 흘려주고, 실제 유량이 흘려주는 것만큼 역방향에는 유량을 빼준다. 유량을 빼준다는 것의 의미는 그 유량만큼 순방향으로 흐르는 유량을 빼줄 수 있다는 의미로 이해하면 된다.

 

Network Flow, DFS로 해결하는 과정  (그림 : 다른 블로그 참조 / 출처는 아래에 표기)

 

위와 같은 노드 / 간선 사이에서 S → T로 흐를 수 있는 최대 유량을 구하는 상황을 가정해보자. DFS를 돌리니 당연히 랜덤하게 돌아가겠지만, 특정 케이스로 돌아갔다고 가정해보자.

S → A → E → T로 유량이 흘렀다고 가정해보자. 총 흐를 수 있는 유량은 최소값인 3이 된다. 따라서 순방향 간선에 3을 모두 더해주고, 역방향 간선에 3을 빼준다. (역방향 간선은 표현되지 않음) 

S → B → E → T로 유량이 흘렀다고 가정해보자. 총 흐를 수 있는 유량은 최소값인 2가 된다. 따라서 순방향 간선에 2을 모두 더해주고, 역방향 간선에 2을 빼준다. (역방향 간선은 표현되지 않음) 

S → C → F → T로 유량이 흘렀다고 가정해보자. 총 흐를 수 있는 유량은 최소값인 4가 된다. 따라서 순방향 간선에 4을 모두 더해주고, 역방향 간선에 4을 빼준다. (역방향 간선은 표현되지 않음).

이 상황에서 보면 더 이상 유량이 흐를 수 있는 경로는 없어보인다. 왜냐하면 순방향만 바라봤을 때, "Capacity[here][next] - Flow[here][next]"를 만족하는 경로가 더는 없어보이기 때문이다. 이 때, 앞서 이야기 했던 역방향 개념이 들어온다. 

S → C → F까지 유량이 흘렀다고 가정해보자. 이 때, F에서 흐를 수 있는 경로는 E 밖에 없다. 왜냐하면 E의 현재 유량은 0이고, 최대 용량은 1이기 때문이다. 따라서 1만큼 유량이 흐를 수 있다. 그럼 S → C → F → E 경로로 유량이 흐를 수 있는 상황이다.

E에 도착한 후 흐를 수 있는 유량을 찾아본다. 순방향으로는 더 흐를 수 있는 경로가 없어보인다. 그렇지만 역방향 경로를 바라보면 흐를 수 있는 경로가 있다는 것을 알 수 있다. E → A로 유량이 흐를 수 있다. 현재 E → A 경로의 유량은 -3이고, 최대 용량은 0이기 때문이다. "0 - (-3) = 3 > 0"이기 때문이다. 따라서 E → A로 유량이 흐를 수 있고, 앞서 흐르던 유량인 1만큼 E → A로 흐를 수 있다. 

S → C → F → E → A로 유량이 1만큼 흐를 수 있는 상황이다. A에서 흐를 수 있는 경로를 찾아본다. 역방향도 흐를 수 있고, 순방향도 흐를 수 있다. 순방향으로 최대 1만큼 흐를 수 있는 것을 확인했기 때문에 A → D → T로 유량을 흘리면 된다. 

최종적으로는 다음과 같이 모든 경로를 탐색한다. 의아한 부분은 S →  C → F → E → A → D → T 경로가 뭐냐 일 수 있겠다. 나는 개인적으로는 이렇게 이해를 했다. 

개념적으로는 S → C → F → E → T로 유량이 1만큼 흘렀다고 이해한다. 그렇지만 실제로 DFS 탐험은 E → A → D → T 형식으로 했다. 이 말은 이 경로부터는 기존에 A → E로 흐르던 유량을 1만큼 다시 흡수하고, 흡수한 유량을 다른 경로로 보내는 형식으로 이해를 하면 된다. 정리하면 DFS 탐험은 DFS 탐험이고, 그것의 해석은 유량을 다시 뒤로 흘렸다로 이해를 하면 될 것 같다. 

 

Network Flow, DFS 최악의 과정

위 같은 경우가 최악의 경우다. 이 경우 2번만에 알 수 있는 최대 유량 값을 2000번 루프를 돌려야 알 수 있게 된다. 지금은 유량이 1000이라 다행이지만, 값이 커지면 비록 노드 4개지만 반드시 시간초과가 날 수 밖에 없다. 왜냐하면 아래 루프로 돌기 때문이다.

1. S → A → B → T로 1만큼의 유량이 흐른다.

2. S → B → A → T로 1만큼의 유량이 흐른다. (B → A는 흐를 수 있는 경로고, 이 때 흐를 수 있는 최소 유량이 1이기 때문)

위의 1,2번 과정을 돌 수 있는만큼 반복하기 때문에 너무너무 오랜 시간이 걸리게 된다. DFS로 하는 이상 저런 경우는 피할 수 없는 경우인 것 같다. 그래서 BFS로 하는 대안이 나왔다. 

 

Network Flow, BFS로 확인하기

최대 유량을 DFS로 구할 경우 위와 같이 치명적인 단점이 발생한다. 따라서 BFS를 이용해서 저런 경우를 방지하면서 좀 더 빠르게 구할 수 있다. BFS로 구할 때는 아래 의사 코드로 최대 유량을 구할 수 있다. 

1. 시작점에서 도착점까지 갈 수 있는 최단 경로를 BFS로 구한다. 이 때, 방문 체크 배열을 관리하고 방문 체크 배열에는 이전 노드가 어떤 것인지 기록해둔다. 만약 도착점에 도착하지 못한다면 종료한다.
2. 도착점부터 이전 방문 노드를 거슬러 올라가며 순방향으로 흐를 수 있는 최소 유량을 기록한다.
3. 도착점부터 이전 방문 노드에 순방향으로 최소 유량을 더하고, 역방향으로는 최소 유량을 뺀다.