BOJ 백준 17481 최애 정하기

 

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

 

[ 문제 요약 ]

• 사람들과, 각 사람들이 좋아하는 걸그룹 멤버가 주어지면 1:1로 최대 매칭할 수 있는 횟수를 출력하는 것입니다.
• 전부 매칭이 가능한 경우, YES 출력, 아닌 경우 NO 출력 후 최대 매칭 가능한 횟수를 출력합니다.

 

[ 테스트 케이스 설명 ]

6 6			// 친구수 N(2<=1,000), 그룹 멤버 수 M(2<=1,000)
MIYEON			// M줄에 걸쳐 멤버의 이름이 최대길이 100글자로 영어대문자로 주어짐
MINNIE
SOOJIN
SOYEON
YUQI
SHUHUA
2 YUQI SOOJIN		// N줄에 걸쳐 친구 별로 좋아하는 멤버 수 K(1<=M)와 해당 그룹의 멤버 이름이 주어짐
1 SOYEON
1 YUQI
2 YUQI SHUHUA
3 MIYEON SOYEON YUQI
3 MIYEON SHUHUA SOYEON
//답, 각 매칭이 모두 가능한지 여부를 가능하면YES출력, 불가하면 NO출력 후 다음 줄에 최대한 겹치지 않게 매칭할 수 있는 최대 수를 출력
NO
5

 

 

[ 알고리즘 분류 ]

• 자료 구조
• 해시를 사용한 집합과 맵
• 이분 매칭

 

[ 문제 해설 ]

 

일반적인 이분 매칭 문제입니다. 각 사람이 좋아하는 멤버가 주어질 때, 각 멤버는 문자열이기 때문에 숫자로 변환을 위해 HashMap을 사용합니다.

 

그 후 일반적인 이분 매칭 알고리즘으로 문제를 풀어주면 됩니다.

 

이분 매칭은 두 그룹 간 가능한 최대 매칭을 찾는 알고리즘으로, 그래프 이론에서 널리 쓰이며 네트워크 연결, 작업 분배 등 실생활 문제에도 활용됩니다.

 

여기서 dfs 함수는, 입력되는 i가 매칭이 가능한지, 가능하지 않은지를 반환합니다. i는 사람을 의미하며, dfs 함수안에서 이미 매칭된 걸그룹 멤버가 있다면, 그 걸그룹 멤버에 매칭된 사람에게, 다른 걸그룹 멤버에게 갈 수 있는지 계속해서 묻습니다.

 

무한 루프를 방지하기 위해 한 dfs 함수마다 땅굴의 방문 유무를 체크하는 visit 배열을 초기화해 이용합니다.

 

마지막으로 문제에서 땅굴에 들어가지 못한 들쥐를 출력하라 하였으므로 총 들쥐 수에서 땅굴에 들어간 수를 빼 출력합니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;
class Main{
	
	static int N, M;
	static int match[];
	static boolean visit[];
	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());
		M = Integer.parseInt(st.nextToken());
		match = new int[M + 1];
		visit = new boolean[M + 1];
		adList = new ArrayList[N + 1];
		
		HashMap<String, Integer> map = new HashMap<>();
		for(int i=1; i<=M; i++)
			map.put(br.readLine(), i);
		
		for(int i=1; i<=N; i++)
		{
			adList[i] = new ArrayList<>();
			st = new StringTokenizer(br.readLine());
			int k = Integer.parseInt(st.nextToken());
			while(k-->0)
				adList[i].add(map.get(st.nextToken()));
		}
		
		int cnt = 0;
		
		for(int i=1; i<=N; i++)
		{
			Arrays.fill(visit,false);
			if(dfs(i))
				++cnt;
		}
		
		System.out.print(cnt == N ? "YES" : ("NO\n" + cnt));
	}
	static boolean dfs(int person)
	{
		for(int member : adList[person])
		{
			if(visit[member])
				continue;
			
			visit[member] = true;
			if(match[member] == 0 || dfs(match[member]))
			{
				match[member] = person;
				return true;
			}
		}

		return false;
	}
}