BOJ 백준온라인져지 11375 열혈강호 풀이

이분 매칭 문제를 엄청 오랜만에 풀어봤다.

https://en.wikipedia.org/wiki/Matching_(graph_theory)

http://koosaga.com/18

http://1ambda.github.io/algorithm/algorithm-part2-5/

위 링크에 많은 설명이 있고, 읽지는 않았다.

이 문제를 풀이한 방법은 아주 기초적인 DFS 를 이용한 O(V * E) 이다.

오늘은 시간이 없어서 이론보다는 구현을 목적으로 공부했다.

풀이 방법

1. 사람을 한명씩 dfs 로 연결할 수 있는 일을 잡는다.

2. 이미 연결돼있는 선이라면 그 선에 연결된 사람이 다른 일을 잡을 수 있는지 확인한다.

3. 반복

4. 끝