Edmonds-Karp

카테고리: Algorithm

출처 꼭 봐야하는 킹갓제네럴동빈 유튜브

사용 언어 자바

Jack R. Edmonds라는 신성한 외계인께서 설파하신 알고리즘으로

그래프의 한 정점에서 다른 정점까지 물을 흘려보낼 때
동시에 최대 얼마까지 보낼 수 있는지 구하는 알고리즘이다

간선(배수관)은 한방향으로 흐르며 현재 흐르고 있는 유량과
최대로 흐를수 있는 용량 정보를 가지고 있다

단순히 출발 정점에서 도착 정점까지 가능한 경로들을 구하고
경로의 간선들 중에 최저 용량이 그 경로의 낭비없는 최대 출력량이다
경로에 포함된 간선들마다 #유량에서 출력량을 더해 중첩문제를 처리하면
쉽게 답을 구할 수 있다

그런줄 알았다

사람이 구하면 대충 적절한 곳을 조합해보고 어렵지 않게 답을 찾을수 있다
근데 이걸 논리적으로 표현할 땐 ‘대충 적절한 곳’이라고 할 수 없다

그래서 Jack R. Edmonds께서는 배수관을 한방향으로 보지 않았다
그 분께서 존재하시는 우주의 배수관은 한방향으로만 흐르지 않았던 것

그는 #유량에 출력량을 더해주고나서, 간선(배수관) 반대편의 입장에서
반대 방향의 간선을 만들어 유량에서 출력량을 빼줬다
새로 만들어진 반대 방향의 간선은 음수의 유량과 0의 용량을 가졌다

절대적인 방향을 가지고 흐르지 않는 현실을 논리적으로 표현해낸 것이다
현실(유량을 한도로 역방향도 이동가능)이 반영되자 경로들은 늘어났고
비로소 모든 경우의 수를 계산할 수 있게 됐다

이 알고리즘을 이해한 순간 정말 기분이 성스러워졌다
난 다른 경우의 수가 있을거라는 의심조차 못했거늘

깨달음을 전해주신 킹갓제네럴동빈님께 감사를 전합니다