BOJ 백준 11375 열혈강호

 

문제 : https://www.acmicpc.net/problem/11375

 

[ 문제 요약 ]

• 직원 수와, 일의 수가 주어지고, 각 직원이 할 수 있는 일의 번호가 주어집니다.
• 이때, 각 직원과 일을 매칭 시킬 때, 매칭 시킬 수 있는 최대 매칭 횟수를 출력합니다.

 

[ 테스트 케이스 설명 ]

5 5	// 직원 수(1<=1,000), 일의 수(1<=1,000)
2 1 2	// 각 직원이 할 수 있는 일의 번호
1 1
2 2 3
3 3 4 5
1 1
// 답
4

 

 

[ 알고리즘 분류 ]

• 이분 매칭

 

[ 문제 해설 ]

 

이 문제는 이분 매칭 알고리즘으로 간단히 풀 수 있습니다.

 

이분 매칭은 두 개의 그룹이 있을 때, 각 그룹의 원소들을 서로 하나씩만 (최대로) 매칭 시키는 알고리즘입니다. 실생활에서 많이 쓰이며 dfs를 통해 간단히 구현할 수 있는, 구현에 특정한 틀이 있는 알고리즘입니다.

 

여기서는 사람을 일에 매칭 시키는 것으로 보고, 한 사람씩 순회하며 그 사람이 다른 일들과 매칭 가능한지를 탐색하는 dfs 함수를 만듭니다.

 

dfs 함수 안에서는 지금 탐색하려는 사람이 매칭이 가능한지를 true, false로 반환합니다.

 

이 dfs 함수 안에서는 각각의 일에 따른 매칭된 사람 번호를 관리하는 job 배열을 둡니다. job 배열의 인덱스는 일의 번호고, 그 안에 저장된 value가 매칭된 사람 번호입니다.

 

그리고 특정 사람이 매칭 가능한지를 탐색하기 위해 이미 매칭된 다른 모든 사람에게 다른 job으로 이동 가능한지 물어봅니다. 이렇게 모든 사람에 묻기 위해 재귀를 사용합니다.

 

아래는 각각 코드 2개를 보여줍니다.

 

첫 번째 코드는 인접 리스트를 표현 시 List 자료구조를 사용했고, 두 번째 코드는 배열을 사용한 코드입니다.

 

속도가 거의 2배가량 차이 납니다.

 

[ List 사용 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Main{
	
	static int N;				// 직원 수
	static int M;				// 일의 최대 수
	static int[] job;			// 각일에 대해 현재 매칭된 사람을 담을 배열, idx가 일의 번호, value가 매칭된 사람
	static boolean[] jobVisit;	// 인덱스가 일의 번호를 의미하며, 해당 일을 방문 해서 체크했는지를 저장
	static ArrayList<Integer> []adList;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N		= Integer.parseInt(st.nextToken());// 직원 수(1<=1,000)
		M		= Integer.parseInt(st.nextToken());// 일의 수(1<=1,000)
		adList	= new ArrayList[N + 1];
		job		= new int[M + 1];
		
		for(int i=0; i<=N; i++)
			adList[i] = new ArrayList<>();
		
		for(int i=1; i<=N; i++)
		{
			st = new StringTokenizer(br.readLine());
			int j = Integer.parseInt(st.nextToken());
			while(j-->0)
			{
				adList[i].add(Integer.parseInt(st.nextToken()));
			}
		}
		
		int cnt = 0;

		for(int person=1; person<=N; person++)
		{
			jobVisit = new boolean[M + 1];
			if(dfs(person))
				++cnt;
		}
		System.out.print(cnt);
	}
	static boolean dfs(int person)
	{
		for(int jobNumber : adList[person])
		{
			if(jobVisit[jobNumber])
				continue;
			
			jobVisit[jobNumber] = true;
			
			if(job[jobNumber] == 0 || dfs(job[jobNumber]))
			{
				job[jobNumber] = person;
				return true;
			}
		}
		return false;
	}
}

 

 

[ 배열 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	
	static int N;				// 직원 수
	static int M;				// 일의 최대 수
	static int[] job;			// 각일에 대해 현재 매칭된 사람을 담을 배열, idx가 일의 번호, value가 매칭된 사람
	static boolean[] jobVisit;	// 인덱스가 일의 번호를 의미하며, 해당 일을 방문 해서 체크했는지를 저장
	static int[][]adList;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N		= Integer.parseInt(st.nextToken());// 직원 수(1<=1,000)
		M		= Integer.parseInt(st.nextToken());// 일의 수(1<=1,000)
		adList	= new int[N + 1][];
		job		= new int[M + 1];
		
		for(int i=1; i<=N; i++)
		{
			st = new StringTokenizer(br.readLine());
			int j = Integer.parseInt(st.nextToken());
			
			adList[i] = new int[j];
			
			while(--j>=0)
				adList[i][j] = Integer.parseInt(st.nextToken());
		}
		
		int cnt = 0;

		for(int person=1; person<=N; person++)
		{
			jobVisit = new boolean[M + 1];
			if(dfs(person))
				++cnt;
		}
		System.out.print(cnt);
	}
	static boolean dfs(int person)
	{
		for(int jobNumber : adList[person])
		{
			if(jobVisit[jobNumber])
				continue;
			
			jobVisit[jobNumber] = true;
			
			if(job[jobNumber] == 0 || dfs(job[jobNumber]))
			{
				job[jobNumber] = person;
				return true;
			}
		}
		return false;
	}
}