[펌] Minimum Cost Flow 1

가중치 방향그래프에서 한 지점에서 다른지점까지 가는 최단 경로를 찾는 방법엔 여러 가지가 있다. 그런데 간선의 가중치가 양수, 음수가 섞여있을 경우에는 Dijkstra 알고리즘은 쓸 수 없고 보통 Bellman-Ford 알고리즘을 쓰게 된다. 단 이것도 '가중치들의 총합이 음수가 되는 사이클'이 그래프 내에 존재하지 않아야 한다는 전제 조건이 있어야한다. 만약 저런 사이클이 존재한다면 '최단 경로'라는 개념 자체가 없어지기 때문이다(그냥 그 사이클대로 무한히 돌면 경로의 길이는 무한히 작아지게 되니까).

또한, 한 지점에서 다른 지점까지 가는 최장 경로는 주어진 그래프의 간선의 가중치에 -1 을 각각 다 곱해준다음 Bellman-Ford를 돌렸을때 나오는 답에 다시 -1을 곱해줌으로써 얻을 수 있다. 물론 이것도 그래프 간선의 가중치에 -1 을 곱했을 당시에 음수 사이클이 없어야 한다는 가정 하에서 이게 성립한다. 즉, 원래 상태의 그래프에서 '가중치들의 총합이 양수가 되는 사이클'이 없어야 Bellman-Ford를 통해서 최장 경로를 구할 수 있다.

사실 Bellman-Ford는 이름은 거창할지 몰라도 쉽게 말해 그냥 큐 하나랑, 정점 크기만큼의 배열(커팅용)을 만들어놓고 BFS 돌려서 찾는 거랑 다를 바 없으니까 딱히 부담가질 필요는 없다. 이론적인 부분에 확신을 갖고 시작하고 싶다면 Bellman-Ford 알고리즘에 대해 더 공부하면 되는 거고..

그런데 뜬금없이 왜 최단/최장 경로를 구하는 법을 알아야 되나? 이제부터 소개할 Minimum Cost Flow 문제들의 풀이에 쓰이기 때문이다.

 

출발지와 도착지가 있는 방향그래프가 있다. 그래프의 방향간선의 가중치에는 두 종류가 있다 - Cost와 Flow 이렇게.
Cost는 그 방향간선을 따라 이동하는데 드는 비용이고, Flow는 최대 얼만큼의 용량이 그 간선을 따라 흐를 수 있는지 나타내는 값이다.
(이전 포스트에서 소개한 문제들에는 방향그래프의 가중치가 Flow 하나밖에 없었다는걸 주목하길 바란다)

만일 출발지에서 도착지까지 가는 어떤 경로가 존재한다면, 그 경로를 통해 1만큼의 흐름이 흐를 때마다 그 경로상의 모든 Cost의 총합 만큼의 비용을 소비하게 된다.
즉 출발지에서 도착지까지 가는 어떤 경로가 있으면, 그 경로에 포함되는 간선들의 Flow의 최소값 만큼의 흐름이 흐를 수 있으므로, 그 경로를 통해 k * (그 경로상의 Cost의 총합) 만큼의 비용을 소비할 수 있다. 여기서 k는 k = 0, 1, 2, …, (그 경로상의 간선들의 Flow의 최소값) 중 하나이다.

이 경우 출발지부터 도착지까지의 최소(혹은 최대) 비용을 구하는 문제이다.

이런 문제를 Minimum(혹은 Maximum) Cost Flow Problem 이라 한다. 최대 비용을 구할 때에도 그냥 Minimum Cost Flow 라고 쓰기도 한다. 어차피 본질적으론 같은 문제니까.

 

 

Minimum Cost Flow 문제 유형은 크게 출발지로부터 도착지까지의 흐름이 얼마라고 딱 정해져 있는 경우와 그렇지 않은 경우 이렇게 두가지로 볼 수 있다.

전자의 경우 중에서, 정해진 흐름의 양이 그 그래프의 Maximum Flow와 같다면 그 문제를 특별히 Minimum-Cost Maximum-Flow Problem 이라고 하고 줄여서 MCMF라고 하기도 한다.

(여기서 중요한게... MCMF라고 쓰면 통상적으로 방금 말한 Minimum-Cost Maximum-Flow Problem을 가리키며, 이전 포스팅에서 소개한 Minimum-Cut Maximum-Flow theory를 가리키진 않는다. 헷갈리는 사람이 간혹 있다.
Minimum-Cut Maximum-Flow theory는 Minimum-Cut과 Maximum-Flow 이 두 문제가 서로 동치라는 이론을 말하고,
Minimum-Cost Maximum-Flow problem은 출발지로부터 도착지까지의 최대의 Flow를 가지는 경우들 중 Cost의 최소값을 구하는 문제이다.
Cut이냐 Cost냐 단어 하나에 따라 의미는 천지 차이가 된다)

참고로 헝가리안 메소드를 통해 풀 수 있는 모든 문제는 MCMF로도 풀 수 있고,
그래프의 모든 간선의 Cost를 0으로 해놓은 MCMF 문제는 이전 포스팅에서 소개한 Maximum Flow 문제와 동치가 된다.

이제 각 유형에 대해 문제들을 살펴보자.

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

첫번째 유형 - 출발지로부터 도착지까지의 흐름이 정해져 있는 경우이다. 다음 문제를 보자.

PKU 3422 - Kaka's Matrix Travels
http://poj.org/problem?id=3422

N * N 체스판의 각 칸에 음이 아닌 정수가 하나씩 써져 있다. Kaka는 SUM이라는 변수를 가지고 체스판의 가장 좌측 상단에서 출발하여 가장 우측 하단에 도착하는 여행을 하는데, 다음과 같은 규칙을 만족하면서 이동한다. 처음에는 SUM=0이다.

1. 한번에 오른쪽으로 1칸 혹은 아래쪽으로 1칸 이동할 수 있다.
2. Kaka가 위치한 칸의 숫자를 SUM 값에 더한 후, 그 칸의 숫자를 0으로 바꿔버린다.

Kaka가 여행을 1번 하는 경우, 얻을 수 있는 SUM 값의 최대값을 구하는 것은 어렵지 않다. 이제 Kaka가 여행을 K번 하는 경우 얻을 수 있는 SUM 값의 최대값을 구하여라. 여행을 할 때마다 SUM 값은 누적되며, N은 최대 50, K는 최대 10, 체스판에 써있는 숫자는 최대 1000이다.

입력
첫 줄에 N, K가 들어오고, 다음 N개의 줄에 N * N 체스판에 쓰여진 수가 주어진다.

출력
SUM의 최대값을 출력한다.

입력 예
3 2
1 2 3
0 2 1
1 4 2

출력 예
15

 

--

 

K=1일 경우 그냥 다이나믹으로 풀면 된다. K가 2 이상일 경우 문제가 복잡해진다.

그냥 다이나믹을 K번 돌리면 안되나? 라는 생각이 들 수도 있는데, 그렇게 하면 다음과 같은 입력에서 성.. 아니, 안좋은 사태가 발생한다.

3 2
1 2 6
4 5 8
7 3 1

이 입력을 그냥 다이나믹 K번 돌려서 풀어보자.

첫번째 여행 :
0 2 6
0 0 0
7 3 0  (이 때의 SUM은 19)

두번째 여행 :
0 2 6
0 0 0
0 0 0  (이 때의 SUM은 29)

이렇게 해서 29로 답이 구해지는데,

실제의 답은.. 32이다.

첫번째 여행 :
0 0 0
4 5 0
7 3 0  (이 때의 SUM은 18)

두번째 여행 :
0 0 0
0 5 0
0 0 0  (이 때의 SUM은 32)

 

그렇다면 풀이법을 바꿔보자. 이 문제는 위에서 언급한 첫번째 유형의 문제이다. 즉 출발지로부터 도착지까지의 흐름의 양이 정해진 Min-Cost Flow 문제이다.

우선 다음과 같이 체스판 한 칸을 두개의 정점으로 생각하여 그래프를 구성하자. 그래프의 간선에 써있는 숫자는 왼쪽이 Flow(최대 흐름량), 오른쪽이 Cost이다. 최대 흐름량을 무한대로 잡아야 한다면 그냥 K로 두면 된다. 왜냐면 K번 여행을 할 거니까 그 이상의 흐름은 들어올 일이 없기 때문이다. 위 예에서는 K=2이므로 2로 두겠다.

그리고 SUM에 해당하는 변수를 만들고 초기값을 0으로 해둔다.

다음엔 Bellman-Ford를 통해 다음과 같이 출발지로부터 도착지까지의 Cost합이 최대인 경로를 찾고,

(이때의 비용은 1 * (1+0+4+0+5+0+8+0+1) = 19 가 된다)

SUM 값에 해당 비용을 더하고, 찾은 경로에 포함되는 간선들의 flow의 최소값 만큼을 각 간선들의 flow에서 다 빼주고, 그만큼 반대 방향의 flow를 생성한다.

이 과정은 이전 포스트에서 자세히 다루었으므로 익숙할 것이라 믿는다. 그런데 다른 점은, 반대 방향으로 생성하는 flow의 cost 값은 원래 방향의 cost값에 -1을 곱한 값으로 설정해준다.

 

이 상태에서 SUM값(그림의 예에서는 19)은 여행을 1번 했을 때의 최대값이다. 이제 이 과정을 K-1번 만큼 더 해주면 된다.

Cost의 합이 최대인 경로를 찾고...

(이때의 비용은 1 * (0+0+2+0+6+0+0+(-5)+0+0+7+0+3+0+0) = 13 이 된다)

SUM값에 더해주고 경로를 바꿔준다(이 때의 SUM 값은 32).

 

이 과정을 수행한 후의 SUM 값이 정답이 된다. Bellman-Ford를 사용한 이런 일련의 풀이 과정을 Successive Shortest Path 알고리즘이라고 한다.

위 과정에서 볼 수 있듯 이미 지나온 경로를 '취소'하고 이전과는 다른 해를 구하는 과정은 단순히 그리디한 풀이로는 쉽게 따라갈 수가 없다.

주의점으로는, 위 문제는 두 정점 사이에 여러 개의 간선이 존재하는 경우이므로 인접행렬로 코딩하기엔 약간 애로사항이 있을 수 있다는 것이다.

 

비슷한 문제들을 더 소개한다.

--

PKU 3680 - Intervals
http://poj.org/problem?id=3680

요 문제는 구간의 위치 관계에 따라 점과 점 사이에 간선을 그어야 할지 말지만 잘 설정해주면 나머지 과정은 똑같다.
K와 모든 weight가 다 1일 경우는 유명한 그리디(혹은 다이나믹) 문제가 된다.

--

ACM World Final 2006: 3562 - Remember the A La Mode!
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1563

이 문제가 Min-Cost Max-Flow problem의 좋은 예이다. 여기서는 Min-Cost 및 Max-Cost 둘다 구하라고 되어 있다.

보통 이런 류의 문제에서는 풀이 과정에서 '가중치의 합이 음수(혹은 양수)인 사이클'이 나타나지 않는다. 왜 그런지는 귀류법으로 생각해 보시길 바란다.

만일 그런 사이클이 절대 등장하지 않을거라는 확신이 없어 불안할 경우 쓰는 방법이 있긴 한데 이는 맨 마지막에 소개하겠다.

 

 

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

이제 Minimum-Cost Flow 문제의 두번째 유형, 즉 Flow의 양이 정해져 있지 않을 경우를 보자. 이 경우도 딱히 다르진 않다.

최대값을 구해야 된다면 출발지-도착지까지의 경로 중 총 비용이 양수인 경로가 없을 때 까지,
최소값을 구해야 된다면 출발지-도착지까지의 경로 중 총 비용이 음수인 경로가 없을 때 까지 위와 같은 Bellman-Ford를 쓰는 과정을 진행하면 된다.

다음 문제를 보자.

--

제23회한국정보올림피아드(2006.7.14) 고등부 문제 2 - 두부 모판 자르기
http://211.228.163.31/pool/bean_curd/bean_curd.php?pname=bean_curd

문제 내용까지 여기 쓰기엔 여러 개의 그림들도 삽입해야 되서 약간 번거로워서.. 링크를 타고 가서 보길 바란다.

이 문제는 크게 다이나믹과 네트워크 플로우 이렇게 두 가지 풀이법이 있는데, 후자가 시간적 면에서 더 빠르고 머리도 덜 아프다.



이 문제의 다음과 같은 예제 입력에 대한 그래프를 그려보겠다.

입력

3
AAC
FCA
ACB

우선 두부판을 체스판처럼 생각해서 체스판의 까만 칸과 흰 칸을 각각 묶는다는 생각으로 그래프를 아래와 같이 그린다.

간선의 가중치까지 표시하려니 그림이 너무 복잡해질까봐 그림에는 써놓지 않았다. 가중치는 출발지와 도착지에 인접한 간선들은 (1,0)으로, 나머지 간선들은 (1,해당 두 단위두부에 해당하는 가격)으로 각각 설정해 주면 된다.

다음으로, 출발지부터 도착지까지의 경로 중 비용이 최대인 경로를 Bellman-Ford로 찾아서
i) 찾은 비용이 양수라면 답에 더하고 경로를 바꾼 다음 다시 이 과정을 반복하고,
ii) 찾은 비용이 음수라면 더 이상 비용이 양수인 경로는 없는 것이므로 반복을 끝내면 된다.

위 과정을 수행한 뒤 답을 저장하는 변수에 저장돼있는 값이 답이 된다.

 

그렇다면 여기서 몇가지 의문점들을 제기할 수도 있을 것이다.

[의문점 1] 그럼 굳이 매번 비용이 최대인 경로를 찾는 이유가 있나? 그냥 어떤 경로든 비용이 양수이기만 하면 바로 답에 더해주고 경로를 바꿔주고를 반복하면 되는 것 아닌가?

이 의문은 아래 그림 하나로 종결된다.

(비록 이 문제에서 가능한 입력은 아니지만, 문제 풀이 과정에서 충분히 저런 상황이 나올 수 있다)

위의 그림을 언뜻 보면 '올바르지 않은 해를 구할 수도 있어서구나' 라고 이해할 수 있다.

근데 좀더 핵심적인 말로 바꿔보면 다음과 같이 된다 - '합이 양수인 사이클이 존재할 수도 있게 되어서구나'
(이 문제는 Max-Cost를 구하는 것이므로, Cost의 합이 양수인 사이클이 존재하면 안된다)

매번 비용이 최대인 경로를 찾아서 풀이 과정을 반복한다면, 풀이 과정 전체에서 합이 양수인 사이클은 등장하지 않는다 - 왜 그런지는 아까도 언급했듯이 귀류법으로 생각해보면 알 수 있다.

따라서 매번 비용이 최대인 경로를 찾는 것이다.

 

[의문점 2] 이 문제는 MCMF에 해당되는 것 아닌가?

이 의문은 다음 입력 예제를 보면 해결된다.

4
AAAF
AFAF
AAAF
FFFF

위 입력의 경우 정답은 400이지만, MCMF로 풀게 되면 300의 답을 얻을 수 있을 것이다.

이 문제에선 2x1 두부의 개수를 최대로 해야된다는 말이 없으므로 MCMF는 아니고, 위에서 언급한 두번째 유형인 총 유량이 정해져 있지 않은 Min-Cost Flow 문제에 해당되는 것이다.

 

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

마지막으로 음수(혹은 양수) 사이클이 절대 등장하지 않을거라는 확신이 없을 경우 쓰는 방법에 대해 언급하겠다. 나도 직접 짜본적은 없지만..

Bellman-Ford를 돌릴때에 음수 사이클이 존재한다면 알고리즘이 제대로 동작하지는 않지만, 그 음수사이클이 어떤 건지 찾아낼 수는 있다.
만약 그렇게 찾아낸다면, 그 사이클을 쭉 한바퀴 돌면서 간선들의 Flow의 최소값 만큼의 흐름을 다 역방향으로 해주면 된다. 이때 이에 드는 비용도 답 변수에 더해 주어야 한다.

이 과정을 Cycle-cancelling 알고리즘이라 한다.

Cycle-cancelling을 통해 음수 사이클을 없앴다면 Successive Shortest Path 과정을 계속 진행하면 되고, 사이클이 또 생기게 되면 위 과정을 다시 수행해주면 된다.

이에 대한 이론적인 부분은 다음 링크의 Cycle-cancelling 파트를 참고하길 바란다.
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow2
(위 링크는 TopCoder에 어떤 사람이 쓴 Min-Cost Flow Problem 설명인데, 3개 part 중 Part 2의 링크이며, MCF의 이론적인 부분에 대해 더 공부하고 싶은 분들은 Part 1부터 차례로 보시면 될 듯 하다)

 

--

이상으로 네트워크 플로우 설명을 마치겠다.

필자가 직관적인 걸 좋아하나 엄밀한건 그리 좋아하지 않아서, 용어의 정의 및 설명이 명확하지 않거나 틀릴수도 있는데 그런 점이 보이면 가차없는 댓글 부탁드린다.

출처 : http://musicdiary.egloos.com/4213579