[BOJ] 백준 11376 열혈강호 2 (JAVA)

이분매칭!

📑 문제

백준 11376 열형강호

---

🌱 아이디어

이분매칭의 아주 살짝 응용 버전?, 이분매칭의 특징을 알면 풀 수 있다.

 

아마 기본 열혈강호 문제를 풀고 이 문제를 푸는 사람이 많을 것 같다.

 

기본적인 네트워크 플로우, 이분매칭은 1 대 1 매칭이 디폴트이지만 이 문제에서는 1 대 2 매칭까지 가능하다.

즉 사람 한 명이 두 가지 일을 할 수 있다.

 

가장 처음 사람마다 몇 개의 일을 점유했는지 카운트하는 배열을 생성하고 관리하려 했지만 실패했다.

 

하지만 이분매칭의 메커니즘을 자세히 보게 되면

이분매칭 시 한 사람에 대해 한번만 dfs 함수를 호출하는데 => 1 : 1 매칭, 사실 dfs호출을 여러 번 하는 만큼 1 대 N 매칭을 할 수 있다.

 

---

🌱 코드 및 풀이

 

answer < M을 통해 모두 매칭이 되었다면 미리 for문을 빠져나온다.

---

🌱 느낀 점

49번 줄 answer < M 유무 차이.

 

기본 DFS 이용한 이분매칭은 시간이 오래 걸린다. 그래서 모두 점유 시 break를 하도록 구현했더니 시간차이가... 매우 성공적이다!!

네트워크 플로우 알고리즘이 여러 가지 지만 다음엔 홉크로프트 -카프 알고리즘을 공부해야겠다.

 

기존 DFS 이용한 이분매칭은 N, M이 클수록 비효율적이다 반대로 홉크로프트 - 카프 알고리즘은 매우 빠르다!! O(E * sqrt(V))

이젠 세그먼트 트리와 위상정렬도 슬슬 공부하자..