[BOJ] 백준 11376 열혈강호 2 (JAVA)
Algorithm/- Baekjoon2024. 6. 28. 00:24[BOJ] 백준 11376 열혈강호 2 (JAVA)

📑 문제🌱 아이디어이분매칭의 아주 살짝 응용 버전?, 이분매칭의 특징을 알면 풀 수 있다. 아마 기본 열혈강호 문제를 풀고 이 문제를 푸는 사람이 많을 것 같다. 기본적인 네트워크 플로우, 이분매칭은 1 대 1 매칭이 디폴트이지만 이 문제에서는 1 대 2 매칭까지 가능하다.즉 사람 한 명이 두 가지 일을 할 수 있다. 가장 처음 사람마다 몇 개의 일을 점유했는지 카운트하는 배열을 생성하고 관리하려 했지만 실패했다. 하지만 이분매칭의 메커니즘을 자세히 보게 되면이분매칭 시 한 사람에 대해 한번만 dfs 함수를 호출하는데 => 1 : 1 매칭, 사실 dfs호출을 여러 번 하는 만큼 1 대 N 매칭을 할 수 있다. 🌱 코드 및 풀이 answer 🌱 느낀 점 기본 DFS 이용한 이분매칭은 시간이 오래 걸..

반응형
image