좋아요!
이번에는 이분 매칭(Bipartite Matching) 문제를 하나 골라서, 문제를 정리하고, 입력 예제와 함께 자바(Java) 코드 + 한 줄 한 줄 꼼꼼하게 해설을 드릴게요.
여기서 쓸 문제는 유명한 이분 매칭 문제 중 하나인 백준 11375번 열혈강호를 골라보겠습니다.
📝 문제 (요약)
여러 명의 직원(N명)과 여러 개의 일(M개)이 있다.
각 직원마다 할 수 있는 일이 주어진다. 한 사람은 한 가지 일만 맡을 수 있고, 한 가지 일에는 한 사람만 맡을 수 있다.
이때 할 수 있는 일의 수를 최대화하는 프로그램을 작성해라.
🧪 입력 예제
5 5
3 1 2 3
1 1
1 2
1 3
1 5📜 의미
- N = 5 (직원 수), M = 5 (일의 수)
- 1번째 직원 → 1,2,3번 일 가능
- 2번째 직원 → 1번 일 가능
- 3번째 직원 → 2번 일 가능
- 4번째 직원 → 3번 일 가능
- 5번째 직원 → 5번 일 가능
이 경우 최대로 맡을 수 있는 일 수 = 4개.
🎯 정답
4🔍 이분 매칭 아이디어
이 문제는 이분 그래프를 만들 수 있어요. 한쪽은 직원 집합, 다른 쪽은 일 집합.
간선을 "할 수 있는 일"로 이어주고, 최대 매칭을 찾습니다.
→ DFS를 이용해 증대 경로를 찾는 Hungarian Algorithm을 구현!
🧑💻 Java 코드와 한 줄씩 디버깅식 해설
이제 코드를 볼까요. 코드를 먼저 보여주고, 아래에서 한 줄 한 줄 뜯어서 예제와 함께 설명할게요.
💻 Java 코드
import java.util.*;
public class Main {
static int N, M;
static ArrayList<Integer>[] adj; // 직원별 가능한 일 리스트
static int[] job; // 각 일에 할당된 직원 번호
static boolean[] visited; // dfs용 방문 체크
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt(); // 직원 수
M = sc.nextInt(); // 일 수
adj = new ArrayList[N+1]; // 인덱스 1~N
for (int i = 1; i <= N; i++) {
adj[i] = new ArrayList<>();
int cnt = sc.nextInt();
for (int j = 0; j < cnt; j++) {
int work = sc.nextInt();
adj[i].add(work); // i번째 직원이 work 일 가능
}
}
job = new int[M+1]; // job[j]: j번째 일 맡은 직원 번호(없으면 0)
int ans = 0;
for (int i = 1; i <= N; i++) {
visited = new boolean[M+1]; // dfs마다 초기화
if (dfs(i)) ans++;
}
System.out.println(ans);
}
static boolean dfs(int employee) {
for (int work : adj[employee]) {
if (visited[work]) continue;
visited[work] = true;
// work가 아직 안 배정되었거나 배정된 직원을 다른 일로 보낼 수 있다면
if (job[work] == 0 || dfs(job[work])) {
job[work] = employee;
return true;
}
}
return false;
}
}🕵♂️ 한 줄 한 줄 디버깅식 자세한 해설
✅ 전역 변수
static int N, M;
static ArrayList<Integer>[] adj;
static int[] job;
static boolean[] visited;N,M: 직원 수와 일 수adj: 각 직원마다 가능한 일 리스트job:job[j] = i이면 j번 일은 i번 직원에게 할당됨visited: DFS에서 이미 검사한 일 방지용
✅ main() 내부
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();예제 5 5 → N=5, M=5
adj = new ArrayList[N+1];
for (int i = 1; i <= N; i++) {
adj[i] = new ArrayList<>();
int cnt = sc.nextInt();
for (int j = 0; j < cnt; j++) {
int work = sc.nextInt();
adj[i].add(work);
}
}여기서 예제 입력을 읽어요.
- i=1 → cnt=3 → 일 1,2,3
- i=2 → cnt=1 → 일 1
- i=3 → cnt=1 → 일 2
- i=4 → cnt=1 → 일 3
- i=5 → cnt=1 → 일 5
이렇게 adj가 채워지면 아래와 같이 보관:
adj[1] = [1,2,3]
adj[2] = [1]
adj[3] = [2]
adj[4] = [3]
adj[5] = [5]job = new int[M+1]; // 일 1~M의 주인 직원
int ans = 0;
for (int i = 1; i <= N; i++) {
visited = new boolean[M+1]; // 새롭게 초기화
if (dfs(i)) ans++;
}이 부분은 N명의 직원마다 dfs() 호출.
- 한 명마다 "이 직원이 새롭게 일 맡을 수 있나?" 검사
ans++= 일 하나 맡을 수 있으면 카운트 증가
✅ dfs(int employee)
이 부분이 핵심!
for (int work : adj[employee]) {
if (visited[work]) continue;
visited[work] = true;
if (job[work] == 0 || dfs(job[work])) {
job[work] = employee;
return true;
}
}-
i번째 직원이 할 수 있는 일
work에 대해서:- 아직 검사 안 한 일이라면 검사.
job[work] == 0→ 현재 이 일이 비었으므로 채우고 return true.- 아니면 이미 다른 직원에게 할당됨 → 그 직원을 다른 일로 보내려 시도(
dfs(job[work])) - 만약 성공한다면 이 일을 내 것으로 하고 return true.
🕵♂️ 예제 직원 1 → 일 1
-
i=1
- visited[1]=true, job[1]=0 → job[1]=1, ans++.
-
i=2
- 일1 검사: visited[1]=false→true, 이미 job[1]=1.
- dfs(1) 호출 → 하지만 visited[1]=true이므로 넘어감 → false 반환 → ans 변함없음
-
i=3
- 일2 검사: 비어있으므로 job[2]=3 → ans++.
-
i=4
- 일3 검사: 비어있으므로 job[3]=4 → ans++.
-
i=5
- 일5 검사: 비어있으므로 job[5]=5 → ans++.
최종 ans=4
🎉 출력
4💡 요약
✅ 이 문제를 이렇게 풉니다:
- 이분 매칭 구조를 만든다.
- **DFS(증대경로)**를 이용하여 매번 한 명의 직원이 새로운 일 맡을 수 있는지 검사.
job[]배열로 일의 현재 주인을 추적.visited[]배열로 한 번의 dfs 호출마다 검사했던 일은 중복 검사 안 함.
good