boj 1298 : 노트북의 주인을 찾아서, 2188 : 축사 배정

boj 1298 : 노트북의 주인을 찾아서

boj 2188 : 축사 배정

https://www.acmicpc.net/problem/1298

https://www.acmicpc.net/problem/2188

두 문제 모두 이분매칭의 1번문제이다.

이분매칭 문제를 모든 경우를 고려할 경우 시간복잡도는 N!로 N이 웬만큼 작지 않으면 해결할 수 없다.

"네트워크플로우 -> 이분매칭" 으로 이어지는 공부 과정을 거쳐야 풀수 있는 문제이다.

이분매칭 문제는 위와같이 단순한 형태의 네트워크 플로우 모형으로 바뀌고, 동시에 "가장 매칭쌍이 많으면 몇개일까?" 라는 질문은 "source에서 sink로 최대 얼마나 흘려줄 수 있을까?" 라는 질문으로 바뀐다.

이후 포드 퍼커슨 알고리즘을 이용하여 네트워크 플로우의 최대 흐름을 구하면 된다.

알고리즘을 간략하게 설명하면

1. sink까지 더 흘러줄 수 있는 경로가 존재하면

2. 더 흘려준다.

3. 더이상 흘려줄 수 있는 경로가 존재하지 않을 때까지 1,2과정을 반복한다.

1. 흘러줄 수 있는 경로를 찾음. 흘려준다.

2. 흘려줄 수 있는 경로를 찾음. 흘려준다.

->방향으로 흘려주었다는 것은 <-방향으로 흘려줄 수 있다는 뜻.

3.최종 매칭 결과

DFS를 이용하는지 BFS를 이용하는지에 대한 통찰은 아직 부족하지만, 검색결과 일반적인 네트워크 플로우 모형에서는 BFS를 사용하는 것이 빠르지만, 이분매칭에서는 DFS를 이용하여도 된다고 한다.