컨텐츠 바로가기

Network Flow (1)

http://musicdiary.egloos.com/4207458


네트워크 플로우는 시작점과 끝점이 있는 방향그래프에서의 "흐름"에 초점을 둔 문제 접근 방식이다. 여기서 시작점은 그 점에서 다른 정점으로 나가는 간선만 있는 점이고, 끝점은 그 점으로 들어오는 간선만 있는 점이다. 여기 올리는 네트워크 플로우 관련 포스팅들에는 엄밀한 증명 같은 이론적인 부분은 생략하도록 하겠다.

네트워크 플로우는 단순한 그리디로 풀기엔 곤란한 문제를 쉽게 풀 수 있게 해준다. 간단한 예로 다음 문제를 보자.


----------------------------------------------------------------------------------------------------------------

http://211.228.163.31/pool/stall/stall.php?pname=stall


농부 존은 최신 기술을 접목해서 새로운 축사를 지었다. 그러나 기계적인 문제로 모든 축사가 동일하지는 않다.

처음에는 임의로 소들의 우리를 배치했더니 , 어떤 소들은 특정 우리에서는 젖을 생산하지 않았다. 그래서 이때 까지의 데이터를 수집해서 각 소들이 좋아하는 우리 번호를 알수 있었다.

한 우리에 한 마리의 소만이 할당될 수 있고 , 한마리의 소는 한 우리에만 들어 갈 수 있을 때 최대 매칭 수를 구하는 게 문제이다.

입력 형식
첫 라인은 두 개의 정수 N (0 <= N <= 200) and M (0 <= M <= 200)이 주어진다.
N 은 소 마리수이고 M 은 소 우리의 수이다. 다음 N 라인에는 각 소들이 좋아하는 우리 수가 주어진 후 우리 번호가 주어진다.

출력 형식
최대 매칭 수를 출력한다.


입출력 예

입력

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

출력

4

 


 


그리디로 이 문제를 짠다면 데이터에 따라 AC를 받을 수도 있겠지만 뭔가 완벽한 풀이라는 확신이 없어 찝찝함이 남을 수도 있을 것이다. 이 문제를 네트워크 플로우로 접근하여 푼 풀이를 아래에 소개한다.

 


쉬운 설명을 위해 다음과 같은 입력에 대해 풀이를 하겠다.

3 3
2 1 2
2 2 3
1 1


우선 N+M+2개의 정점을 만든다. N개의 정점은 각각의 소들, M개의 정점은 각각의 소 우리들에 해당한다. 남는 두 정점중 하나는 시작점, 나머지 하나는 끝점으로 하여, 시작점에서 각각 N개의 소들에 해당하는 정점들을 향한 방향간선 N개를 만들고, 마찬가지로 M개의 우리들에 해당하는 정점들 각각에서 끝점을 향한 방향간선 M개를 만든다. 그리고 어떤 소에 대해 그 소에 해당하는 정점으로부터 그 소가 좋아하는 우리에 해당하는 정점들을 향한 방향간선을 다 긋는다.

아래 그림에서 하늘색이 소에 해당하는 노드이고, 노란색이 소 우리에 해당하는 노드이다.


방향그래프가 완성되었다. 이제 답을 구하기 전의 마지막 준비로 s 라는 변수를 만들고 초기값을 0으로 설정해두자.


이제 이 방향그래프에서 시작점에서 끝점으로 가는 경로를 찾는다(BFS로 찾는게 신상에 좋을 것이다).



찾았다면, s값을 1 증가시킨다. 그리고 찾은 경로를 다시 끝점으로부터 시작점까지 쭉 거슬러 올라가면서 경로에 포함된 간선들의 방향을 모조리 반대 방향으로 바꿔버린다. 즉, A→B 인 간선이 찾은 경로상에 있으면 A←B 로 바꾼다.

다 바꿨다면 다시 경로를 찾는다. 찾았다면 s를 1 증가시키고 그 경로의 방향을 다시 반대로 바꾼다. 이 과정을 시작점에서 끝점까지의 경로가 더 이상 존재하지 않을 때까지 반복한다.


(현재까지 s값은 2)

(현재까지 s값은 3)
이제 더이상 경로가 존재하지 않으므로 반복을 멈춘다.


위 과정이 다 끝난 시점에서의 s값(이 예에서는 s=3) 이 문제에서 원하는 답이 된다.

물론 구체적으로 어떤 소가 어떤 우리에 들어가면 되는지에 대한 예도 찾을 수 있다. 위 과정이 끝났다면 끝점에서 시작점으로 가는 길이 3짜리 경로가 s개 존재할 것이고, 그 경로 각각을 따라가면서 경로상에 있는 소와 소 우리를 짝지어주어 s개의 (소, 우리) 순서쌍을 구해낼 수 있다.

위 그림에서 각각의 보라색 경로를 따라가면 어떤 소를 어느 우리에 집어넣어야 하는지 알 수 있다.

 


기본적으로 네트워크 플로우는 이전 단계에서의 해로부터 다음 단계의 해를 구할 때 이전 단계에서의 일부 과정을 필요에 따라 수정하거나 취소할 수 있다는 것이 장점이며, 위에서 봤듯이 "경로의 방향을 거꾸로 바꾼다" 라는 개념이 그것을 가능하게 해 준다.

 

----------------------------------------------------------------------------------------------------------------

이제 그 유명한 min-cut max-flow theory에 대해 알아보자.


아래 방향그래프에 대해, 다음 두 문제를 생각해보자.

1. 방향간선의 가중치는 그 간선을 따라 흐를 수 있는 물의 최대량을 나타낸다고 할 때, S점에서 E점까지 흐를 수 있는 물의 최대 양은 얼마나 될까?

2. S점에서 E점까지의 경로가 없도록 하기 위해 방향간선을 몇 개 없애려고 한다. 방향간선의 가중치는 그 간선을 없애기 위한 비용을 나타낸다고 할 때, S점에서 E점까지의 경로가 존재하지 않도록 간선을 제거하는 최소 비용은 얼마일까?

 

1번 문제는 maximum flow 문제이고 2번 문제는 minimum cut 문제이다. 그리고 놀랍게도 위의 1, 2번 문제는 동치이다!
이에 관련한 이론들은 구글링해보면 많이 나올 것이고 여기서는 그냥 풀이법만 간단히 설명하겠다.

1번 문제 - 즉 maximum flow 문제 기준으로 설명하겠다.

아까처럼 답을 저장하는 변수를 s라고 하고 초기값을 0으로 두자.


시작점부터 끝점까지 이어지는 어떤 경로를 찾았다고 하자. 이 경로를 따라 흐를 수 있는 물의 최대 양은 그 경로상의 방향간선들의 가중치의 최소값이다. 그 최소값을 x라고 하자(아래 예에서는 x=4이다).

그러면 s에 x만큼의 값을 더해주고, 그 경로의 가중치들에서는 x만큼의 값을 각각 다 뺀다. 또한 도착점부터 시작점까지 거꾸로 진행하는 간선들을 새로 생성하고, 가중치를 전부 x로 둔다.

그림에서는 가중치가 0이 된 간선은 그리지 않았다.

이 과정을 시작점부터 끝점까지 물이 흐를수 있는 경로가 없을 때 까지 진행한다(시작점부터 끝점까지의 경로가 존재해도 그 경로상에 가중치가 0인 간선이 있다면 물이 흐를 수 있는 경로가 아니다).

위 과정이 끝난 시점에서의 s값이 답이 된다. 물론 여기서도 역추적을 통해 물이 어떻게 흘러가야 하는지 구해낼 수 있다.

그림 그리기가 귀찮은건 아닌데.. 여기까지 따라오신 분들은 충분히 다음 과정들을 스스로 하실 수 있기 때문에 위 문제에 대해 더이상 그림은 넣지 않겠다. 절대 내가 그리기 싫어서 안 그린게 아니다.



 

풀이법을 이해하더라도 이게 왜 답이 될까라는 의문이 남을 수 있는데, 스스로 예제 입력을 몇개 만들어서 손으로 그리면서 풀다보면 직관적으로 납득이 갈 것이다. 그래도 찝찝하다면 구글링을 해보시길... 난 정말 무책임한 놈임ㅠ

그리고 이쯤되면 눈치챈 분들도 있겠지만 맨 처음 소개한 문제는 그래프의 간선의 가중치를 다 1로 둔 min-cut max-flow 문제라고 할 수 있다.





 

이제 min-cut max-flow 방식으로 풀 수 있는 문제들을 몇개 더 소개한다.

----------------------------------------------------------------------------------------------------------------

PKU 1149 PIGS - http://poj.org/problem?id=1149, http://211.228.163.31/30stair/pigs/pigs.php?pname=pigs
PKU 3614 Sunscreen - http://poj.org/problem?id=3614

전형적인 max-flow 문제들. 만약 간선의 가중치를 무한대로 잡아야 할 필요가 있을 때는 그냥 충분히 큰 값으로 설정해주면 된다.

----------------------------------------------------------------------------------------------------------------

PKU 3041 Asteroids - http://poj.org/problem?id=3041 , http://211.228.163.31/pool/asteroid/asteroid.php?pname=asteroid

이 문제는 난해해 보이나, 문제에 담긴 생각해내기 힘든 어떤 동치 관계를 생각해 낼 수만 있다면 쉽게 풀 수 있다.

----------------------------------------------------------------------------------------------------------------



다음 포스팅에는 Bellman-Ford 알고리즘을 같이 써서 풀 수 있는 네트워크 플로우 문제들을 소개하겠다.

 


덧글|덧글 쓰기|신고