[Java] 백준 9576번: 책 나눠주기

[문제 바로 가기] - 책 나눠주기

📌 유형 : 이분 매칭

처음 봤을 때 공항 문제와 유사하다고 생각하여 Union-Find로 풀어볼까 했지만 어떻게 풀어야할지 모르겠어서 문제 유형을 확인했더니 처음 보는 이분 매칭이였다.

그래서 이분 매칭에 대한 개념부터 찾아봤다.

이분 매칭은 문제처럼 N명의 사람과 M개의 선택지가 있는데 1대 1 매칭만 가능할 때 가장 많은 사람을 매치해야 한다. 이때 N명의 사람은 M개의 선택지 중 여러개를 선택할 수 있다. (그림 참고)

💡 아이디어

이분 매칭에는 i번째 책을 선택했는지 저장할 boolean 타입의 done 배열과 i번째 책이 누구에게 나누어졌는지 저장할 int 타입의 books 배열이 필요하다.

학생 번호가 0부터 시작하므로 books에 -1을 넣어준 후 각 학생이 원하는 책의 번호를 ArrayList에 저장한다. 이때 학생이 원하는 책의 번호는 a부터 b까지므로 for문을 이용해서 모두 넣어준다.

이후 DFS에서 이분 매칭을 시작한다.

1. done 배열은 각 학생이 DFS 탐색을 할 때 독립적으로 체크를 해주어야 하므로 매번 새로 선언해준다.

2. student 리스트의 x번째 학생이 원하는 책들을 탐색한다.
   (1). 이때 해당 책이 이미 고려되었다면 continue, 고려되지 않았다면 해당 책을 true로 체크해준다.
   (2). 해당 책이 아직 아무에게도 나누어지지 않았거나, 이미 나누어졌을 경우에는 해당 책을 가진 사람이 다른 책을 선택할 수 있을 경우 해당 책을 선택한다.

이 과정을 반복하면 학생들에게 최대로 책을 나누어줄 수 있는 경우의 수가 나온다.

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 백준 9576번 책 나눠주기 
 * 이분 매칭 사용
 */

public class Main {
	public static List<Integer>[] student;
	public static boolean[] done; // DFS에서 i번 책을 고려한 적이 있는지
	public static int[] books; // i번째 책이 누구에게 나눠졌는지
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		
		for (int t = 0; t < T; t++) {
			int answer = 0;
			
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			
			student = new ArrayList[M];
			books = new int[N + 1];
			Arrays.fill(books, -1);
			
			for (int i = 0; i < M; i++) {
				student[i] = new ArrayList<>();
				
				st = new StringTokenizer(br.readLine());
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				
				for (int j = a; j <= b; j++) {
					student[i].add(j);
				}
			}
			
			for (int i = 0; i < M; i++) {
				done = new boolean[N + 1];
				if (dfs(i)) answer += 1;
			}
			
			System.out.println(answer);
		}
	}
	
	public static boolean dfs(int x) {
		for (int book : student[x]) {
			if (done[book]) continue;
			done[book] = true;
				
			if (books[book] == -1 || dfs(books[book])) {
				books[book] = x;
				return true;
			}
		}
		return false;
	}
}