[BOJ] 백준 2188번 축사 배정 (Java)

#2188 축사 배정

난이도 : 플레 4

유형 : 이분 매칭

2188번: 축사 배정

▸ 문제

농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다.

첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다. 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다.

농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다.

▸ 입력

첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200)

둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 Si (0 ≤ Si ≤ M)이 먼저 주어지고, 이후 Si개의 축사 번호가 주어진다. 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.

▸ 출력

첫째 줄에 축사에 들어갈 수 있는 소의 최댓값을 출력한다.

 

문제 풀이  

네트워크 플로우와 연계되는 개념인 이분 매칭(Bipartite Matching) 알고리즘 문제이다. 이분 매칭은 이분 그래프에서 최대 매칭을 찾는 문제를 간단하게 이분 매칭이라고 부른다.

• 그룹 A(소)와 그룹 B(축사)를 주어진 대로 연결하고 용량을 1로 하면 해당 그래프의 최대 유량을 구한 뒤 유량이 흐르는 간선을 모으면 최대 매칭이 된다.

 

시뮬레이션

이분 매칭 구현은 포드-폴커슨 알고리즘처럼 증가 경로를 찾은 뒤 유량을 보내는 것을 반복해주면 된다. 문제에서 주어진 예제를 통해 시뮬레이션을 돌려보자.

 

1번 소 축사 배정하기

• 1번 소는 (2, 5)에 매칭이 가능하므로, 일단 2번에 매칭한다.

1번 소 매칭하기

 

2번 소 축사 배정하기

• 1번 소는 (2, 5),
• 2번 소는 (2, 3, 4)에 매칭이 가능하다.
• 2번 소가 가장 먼저 도착한 축사는 2이다. 따라서 1번 소가 다른 축사 배정이 가능한지 확인하고 가능하면 배정을 바꿔준다.
• 1번 소는 5, 2번 소는 2에 매칭한다.

2번 소 매칭하기 (1번 소 재매칭)

 

 

3번 소 축사 배정하기

• 3번 소는 (1, 5)에 매칭이 가능하므로, 1번에 매칭한다.

3번 소 매칭하기

 

4번 소 축사 배정하기

• 4번 소는 (1, 2, 5)에 매칭이 가능하다.
• 1번 매칭? (재귀로 탐색함)
  • 3번 소가 5번에 매칭해야 된다.
  • 그러려면 5번을 점유하고 있는 1번 소가 2번에 매칭해야 된다.
  • 그러면 2번을 점유하고 있는 3번에 매칭해야 된다.
• 따라서 (1번 소 - 2), (2번 소 - 3), (3번 소 - 5), (4번 소 - 1)로 매칭이 된다.

4번 소 매칭(1,2,3번 소 재매칭)

 

 

5번 소 축사 배정하기

• 5번 소는 (2)에 매칭이 가능한데, 2번에 매칭하려면 최종적으로 재귀 탐색을 해보면 4번 소가 다른 곳을 매칭해야 되는데 (1, 2, 5)모두 소들이 점유하고 있으므로 재매칭이 안된다.
• 따라서, 5번 소는 축사를 배정할 수 없다.

 

DFS 탐색으로 축사 배정 로직 만들기

1번 소부터 ~ n번 소까지 순차적으로 탐색하면서, 축사(d)가 비어있거나 그 축사를 점유하고 있는 소가 다른 축사로 들어갈 수 있는 경우에만 현재 소(here)를 nxt 축사에 배정해주면 된다.

static boolean dfs(int here) {
	for(int nxt : list[here]) {
		if(!check[nxt]) {
			check[nxt] = true;
			// 비어있거나 점유 노드에 더 들어갈 공간이 있는 경우 
			if(d[nxt] == 0 || dfs(d[nxt])) {
				d[nxt] = here;
				return true;
			}
		}
	}
	return false;
}

 

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {

	static List<Integer>[] list;
	static boolean[] check;
	static int[] d;
	public static void main(String[] args) throws  IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
			list[i] = new ArrayList<>();
		}
		
		check = new boolean[m+1];
		d = new int[m+1];
		
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			for(int j=0; j<s; j++) {
				list[i].add(Integer.parseInt(st.nextToken()));	
			}
		}
		
		int cnt = 0;
		for(int i=1; i<=n; i++) {
			Arrays.fill(check, false);
			if(dfs(i)) cnt++;
		}
		System.out.println(cnt);
	}
	
	static boolean dfs(int here) {
		for(int nxt : list[here]) {
			if(!check[nxt]) {
				check[nxt] = true;
				if(d[nxt] == 0 || dfs(d[nxt])) {
					d[nxt] = here;
					return true;
				}
			}
		}
		return false;
	}
}