[백준] 11375 열혈강호

알고리즘 공부

[백준] 11375 열혈강호 - 이분매칭

kdhoooon 2022. 1. 7. 19:34

문제

강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.

각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.

각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

풀이

이 문제는 DFS 를 이용해서 브루트포스 알고리즘으로 해결하려 했으나 시간 초과가 났다.

이를 조금 변형하면 되는 문제였다.

이 문제는 이분매칭(Bipartite Matching) 알고리즘을 사용하는 데 네트워크 플로우와 연계되는 개념이라고 한다.

이분매칭이란?

A 집단이 B 집단을 선택하는 방법에 대한 알고리즘이다.

다시 문제로 돌아와 문제의 예시를 가지고 구현 방법에 대해 설명을 하면,

우선 직원은 1, 2, 3, 4, 5

일은 편읜상 A, B, C, D E

로 하고 풀면

1. 우선, 1번 직원은 A, B 일을 해결할 수 있다. A 일을 했다고 가정하고, 우선 1가지 일은 할 수 있으므로 count++을 해준다.

2. 2번 직원은 A 일이 가능하다. 이 때, A가 겹치기 1번직원과 겹치기 때문에 다시 1번직원의 일을 바꿀 수 있는지 여부를 알아본다.

위의 상황이 가능하기 때문에, 우선 최소 두 가지 일이 가능하므로 count++을 한다.

3. 3번 직원은 B, C 일이 가능하다. 우선 B일을 하려고 했는데 그러면 1번직원과 겹치게 된다. 하지만 1번 직원은 더이상 할 수 있는 일이 없기 때문에 불가능하다. 따라서 3번 직원은 C일을 해야한다.

이 경우가 가능하기 때문에, 우선 최소 세 가지 일이 가능하므로 count++을 한다.

4. 4번 직원은 C, D E 일이 가능하다. 우선 C 일을 하려고 하는데 그러면 3번 직원과 겹치게 된다. 하지만 3번 직원은 B 는 1번과 겹쳐서 안되기에 더 이상 할 수 있는 일이 없다. 따라서 4번 직원은 D일을 선택한다.

위 그림과 같이 선택할 수 있기 때문에 최소 네 가지 일이 가능하므로 count++을 한다.

5. 5번 직원은 A 일만 가능하다. 하지만 A 일을 하려고 하면 2번 직원과 겹치게 된다. 2번 직원 역시 더 이상 해결 가능한 일이 없기 때문에 불가능하다.

따라서 4가지 일이 가능하다.

이렇게 우선적으로 선택하고 나중에 오는 직원이 선택했을때 차선택을 찾아가는 방식으로 푸는 것이 이분매칭 방식이다.

DFS 로 이분매칭을 구현할 수 있다.

static boolean dfs(int here) {
	for(int w : person[here]) {
		
		if(visited[w]) continue;
		
		visited[w] = true;
		if(work[w] == 0 || dfs(work[w])) {
			work[w] = here;
			return true;
		}
	}
	
	return false;
}

위 코드를 해석하면 visited 는 각각의 직원이 일을 고르기 시작할 때 false 로 초기화 하여,

해당 수가 한 번이라도 방문해서 다른일로 변경 여부를 확인했는지를 찾는다. (현재의 직원이 가능한 일을 찾기위해)

그 때의 값이 이미 선택된 경우는 0이 아니기 때문에,

선택한 직원이 다른일로 변경이 가능한지 여부를 판단하기 위해 dfs() 재귀적으로 다시 푼다.

0인 경우는 해당 일을 하면 된다.

위 방식으로 모든 일을 배치해주면 된다.

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();

	static int n, m;
	static List<Integer>[] person;
	static int[] work;
	static boolean[] visited;

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

}