BOJ 백준 30976 사랑의 큐피드

 

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

 

[ 문제 요약 ]

• 남, 여의 키가 주어지고, 각 남자와 여자가 선호하는 키의 기준이 주어집니다.
• 여자는 자신의 선호 기준 보다 작은 키의 남자만 연결을 하고, 남자는 자신의 선호 기준 보다 큰 키의 여자만 원합니다. 이때 1 : 1 매칭 가능한 남녀 그룹의 수를 출력합니다.

 

[ 테스트 케이스 설명 ]

 

2 2		// 여학생수(1<=400, 남학생수(1<=400)
168 164	// i번째 여학생의 키
179 183	// i번째 남학생의 키
180 190	// i번째 여학생의 선호기준 ( 여학생은 자신의 선호 기준보다 작은 학생만 )
155 165	// i번째 남학생의 선호기준 ( 남학생은 자신의 선호 기준보다 키가 큰 학생만 )
 답 : 1

 

 

[ 알고리즘 분류 ]

• 이분 매칭

 

[ 문제 해설 ]

 

이 문제는 인접 리스트만 잘 생성해 주면 일반적인 이분 매칭 문제와 똑같이 풀 수 있습니다.

 

남 → 여로 갈 수 있도록 인접 리스트를 생성하되, 남자가 선호하는 여자라 하더라도 여자가 그 남자를 선호하지 않으면 인접 리스트를 생성하지 않게 합니다.

 

이렇게 리스트만 잘 생성하면 일반 이분 매칭 알고리즘으로 간단히 풀 수 있습니다.

 

[ 정답 코드 ]

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

class Main{
	
	static int match[];
	static boolean visit[];
	static List<Integer> adList[];
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());// 여학생수(1<=400)
		int M = Integer.parseInt(st.nextToken());// 남학생수(1<=400)
		int G[] = new int[N + 1];// 여학생의 키
		int B[] = new int[M + 1];// 남학생의 키
		int T[] = new int[N + 1];// 여학생의 선호 기준
		
		match = new int[N + 1];
		visit = new boolean[N + 1];
		adList = new ArrayList[M + 1];
		// 리스트 초기화
		for(int i=1; i<=M; i++)
			adList[i] = new ArrayList<>();
		
		// 여학생의 키 입력
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			G[i] = Integer.parseInt(st.nextToken());
		
		// 남학생의 키 입력
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=M; i++)
			B[i] = Integer.parseInt(st.nextToken());
		
		// 여학생의 선호 기준 입력
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			T[i] = Integer.parseInt(st.nextToken());
		
		// 남학생의 선호 기준을 입력 받으면서 인접 리스트 생성
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=M; i++)
		{
			int h = Integer.parseInt(st.nextToken());// 남학생의 선호기준
			for(int j=1; j<=N; j++)// 모든 여학생 순회
				if(h < G[j] && T[j] > B[i])
					adList[i].add(j);
		}
		
		int cnt = 0;
		
		for(int i=1; i<=M; i++)
		{
			Arrays.fill(visit, false);
			if(dfs(i))
				++cnt;
		}
		
		System.out.print(cnt);
	}
	public static boolean dfs(int boy) {
		for(int girl : adList[boy])
		{
			if(visit[girl])
				continue;
			
			visit[girl] = true;
			
			if(match[girl] == 0 || dfs(match[girl]))
			{
				match[girl] = boy;
				return true;
			}
		}
		return false;
	}
}