네트워크 플로우

이분 매칭 알고리즘을 정리하면서 자료들을 찾다가 이분 매칭 알고리즘이 네트워크 플로우의 일종이라고 해서 찾아보고 정리하게 되었습니다.

네트워크 플로우는 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘입니다.

설명을 위해서 각각의 A,B,C라는 행성이 있고, 우주선은 빛과 같은 속도로 이동할 수 있다고 합시다.

행성 사이에 숫자는 초당 이동 가능한 우주선 숫자입니다.

A 행성에서 C 행성까지 이동을 하려면 B를 거쳐서 이동을 해야합니다.

B에서 C로 이동 가능한 수는 100이지만 A에서 B까지 50밖에 안되므로 나머지 50은 B행성에 막히게 됩니다.

그러므로 이동경로의 최소값을 기준으로 해서 보내야지 안정적으로 보낼 수 있습니다.

위의 사진을 예시로 50/50, 50/100으로 표현을 할 수 있는데 용량(Capacity)과 유량(Flow)라고 합니다.

문제를 통해 자세히 설명하도록 하겠습니다.

기본적으로 최대유량은 BFS(너비 우선 탐색)을 이용하는 것이 일반적입니다. 이 것을 에드몬드 카프 알고리즘이라고 합니다.

0 -> 1 - > 3 -> 5의 경우 최소값이 12이 이므로 각각에 용량에 12를 더해 줍니다.

0 -> 2 -> 4 -> 5의 경우 최소값이 4이므로 4를 더해줍니다.

이제는 이동 가능한 경우를 더 탐색해서
0 -> 2 -> 4 -> 3 -> 5의 경우를 사용하면 됩니다.
최소값을 7로 사용할 수 있으므로 7을 더해준다.

최대 유량은 23이 나온다.