**이 글은 학교 수업 시간에 활용한 발표자료를 가지고 재구성한 글입니다. 다양한 블로그나 사이트로부터 내용과 사진을 참고했으므로 출처를 밝힙니다.**
| 참고자료 출처(감사합니다!) - https://koosaga.com/133
- https://everenew.tistory.com/177 - 알고리즘 트레이닝 - 프로그래밍 대회 입문 가이드, 2판 |
| 최대 유량 문제 |
최대 유량 알고리즘은 고급 그래프 알고리즘입니다. 그래서 어떤 그래프를 어떤 방식으로 다루는지, 이 알고리즘을 어떻게 응용하고 어디에 사용할 수 있는지 설명드리고자 합니다.
이 알고리즘은 소스와 싱크라는 노드가 존재하는 그래프를 다룹니다.
이 문제의 목적은 소스에서 싱크로 흐르는 유량을 최대한으로 만드는 것입니다.
이때, 우리는 몇 가지 용어를 알고 있어야 합니다.
flow(u, v)는 u에서 v로 흐르는 간선의 유량을 말하고 capacity(u, v)는 u에서 v로 흐를 수 있는 간선의 최대 용량을 말합니다. 그래서 다음과 같은 규칙이 성립되고 추후 알고리즘을 짤 때 활용되는 중요한 성질들입니다.
방금 설명한 내용을 그림과 함께 다시 살펴보면 다음과 같습니다.
그럼 이제 본격적으로, "그래서 최대 유량을 어떻게 찾을 수 있는 건데?"라는 궁금증을 풀어봅시다.
| 포드-풀커슨 알고리즘 |
(다시 한 번 언급하지만 본 내용은 여러 블로그로부터 참고한 내용을 가지고 재구성하였습니다.)
알고리즘의 작동 방식 순서로 설명을 해드리겠습니다. 지금 보이시는 그림이 소스와 싱크가 있는 그래프의 초기 상태입니다. 지금 간선마다 v/k꼴로 표현되어 있는 형태는 유량/용량인 것입니다. 지금은 초기 상태니까 모두 0의 유량이 흐른다는 것을 알 수 있습니다.
그 다음으로 이제 어떤 임의의 증가 경로를 찾은 후 그 경로에 흘릴 수 있는 최대의 유량을 흘려줄 것입니다. 그림에서 찾은
임의의 경로는 최대 용량이 3이기 때문에 그만큼 흘려준 것입니다.
이제 컴퓨터는 이 과정을 계속하게 반복하게 될 것입니다. 그러면 아래 보이시는 것처럼 더 이상 소스에서 싱크로 새로운 유량을 보낼 수 없다는 것을 확인하실 수 있습니다.
하지만, 알고리즘은 이렇게 종료되지 않습니다. 더 이상 소스에서 싱크로 유량을 보낼 수 없을 때 구한 유량이 최대 유량이 아닐 수 있기 때문입니다. 위의 그림을 다시 볼까요?
현재는 소스에서 싱크까지 총 5+4=9의 유량이 흐르고 있습니다.
그런데 만약, S-A-D-T로 1만큼 / S-A-E-T로 2만큼 / S-B-E-T로 2만큼 / S-C-F-T로 4만큼 / S-C-F-E-T로 1만큼 흐른다면 총 유량은 10입니다. 이건 무언가 문제가 있는 것이죠.
(이제부터가 사실상 main idea) 그렇다면 '기존에 선택했던 경로를 취소하고, 새로운 경로를 만들 수 있다면 더 개선된 답을 찾을 수 있지 않을까?' 라는 아이디어가 생겨납니다.
바로 역방향 간선을 활용하는 것입니다. 더 이상 소스에서 싱크로 유량을 보낼 수 없을 때, 더 나은 답이 있는지 찾기 위해 활용하는 것입니다. 저희는 아까 규칙 부분에서 유량의 대칭성(flow(u,v) = - flow(v, u))에 대한 내용을 살펴보았죠.
이 역방향 간선이 핵심이기 때문에 이에 대해 더 자세히 알아보겠습니다.
유량이 남아 있는 간선을 통해 3만큼의 유량을 보냈습니다. 그러면 남아 있는, 잔여 유량은
(총 용량 - 현재 흐르고 있는 유량)이겠죠? 아래 그림에서는 잔여 유량이 3-3으로 0인 것입니다.
flow(u, v) = -flow(v, u)을 이용하여 2에서 1로 흐르는 상황을 생각해봅시다.
이 상황에서 2 -> 1로의 잔여 유량은 0-(-3) = 3인 것입니다.
즉, 이 역방향 간선이라는 가상의 간선을 이용하여 흘려줬던 것을 다시 취소할 수 있다는 것입니다.
대략적인 의사코드를 보면 다음과 같을 것입니다. 정방향 간선과 역방향 간선에 대해 잔여 용량을 더하거나 빼는 방식으로 표현할 수 있습니다.
따라서, A -> E로 가는 경로를 1만큼 취소하고 A->D->T로 흘려줄 수 있는 것입니다.
이 알고리즘을 이용하면 최종적으로 최대 유량을 구할 수 있는 것이죠.
이러한 경로 찾기 알고리즘에는 다음과 같은 종류들이 있다는 점도 참고하시면 좋을 것 같습니다.
-> 포드 - 풀커슨
-> 에드몬드 - 카프 : 너비 우선 탐색 이용
-> 용량 조절 알고리즘
| 최대 유량 = 최소컷 |
최대 유량 문제는 최소 컷 문제와 같은 개념으로 연결됩니다.
최소 컷 문제란 간선 중 일부를 제거하여 소스에서 싱크로 가는 경로를 없애되, 제거한 간선의 가중치 합을 최소로 만드는 문제를 말합니다. 그래서 왜 둘이 같은 개념인 걸까요?
최소 컷 문제는 출발점에서 도착점으로 가는 모든 경로를 차단하는 간선들의 용량 합을 최소가 되도록 하는 것이라고 다시 말할 수 있습니다.
제가 모든 경로를 차단하기 위해 몇 개의 간선을 잘랐다고 가정해봅시다. 원래의 그래프에는 최대 8의 유량이 흐르고 있었습니다.
만약 제가 자른 컷의 크기가 7인 경우, 7개의 유량을 없앤다고 해서 모든 경로를 차단할 수 있을까요? 나머지 1의 유량이 그냥 없어지지는 않을 것이기 때문에 모순이 발생합니다.
만약 제가 자른 컷의 크기가 9인 경우라면 출발점에서 도착점으로 가는 모든 경로를 차단할 수는 있을 것입니다. 그러나, 이것이 '최소' 컷은 아니라는 것입니다. 9보다 작은 용량의 컷을 선택하지 못한 최적화가 안 된 선택이 되겠죠.
예시로 설명을 드렸고, 실제로는 최종적으로 최대 유량이 최소 컷과 같을 수밖에 없다는 사실이 수학적으로 증명이 되었다고 합니다.(https://koosaga.com/133)
지금까지 최대 유량, 최소 컷에 대한 메인 알고리즘과 아이디어 대해 소개해드렸습니다. 다양한 글들을 통해 양질의 자료를 얻을 수 있었고 덕분에 저도 이런 글을 쓸 수 있었습니다. 다음에는 관련 문제와 소스코드에 대해서도 다뤄보겠습니다.
https://nomadsjh.tistory.com/75
[백준] 6086번 최대 유량 문제 풀이(c++)
링크 : https://www.acmicpc.net/problem/6086 문제농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기
nomadsjh.tistory.com
많은 도움 되시길 바라겠습니다.
'프로그래밍 > 알고리즘 & 자료구조' 카테고리의 다른 글
| 비선형 자료구조 - 히프(Heap)와 삽입 및 삭제 연산 (0) | 2023.10.19 |
|---|---|
| 자료의 정렬(1) - 버블, 선택, 삽입 정렬 (1) | 2023.09.06 |
| [자료구조] 덱(Deque) - 코딩기록 (0) | 2023.05.05 |
| [자료구조] 큐(Queue) - 코딩기록 (0) | 2023.05.04 |
| [자료구조] 스택(Stack) - 코딩기록 (0) | 2023.05.03 |
