문제 : 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;
}
}
'알고리즘 > 이분 매칭' 카테고리의 다른 글
| BOJ 백준 11377 열혈강호 3 (0) | 2025.05.16 |
|---|---|
| BOJ 백준 4376 Gopher II (2) | 2025.05.15 |
| BOJ 백준 15271 친구 팰린드롬 2 (1) | 2025.05.15 |
| BOJ 백준 17481 최애 정하기 (1) | 2025.05.14 |
| BOJ 백준 14433 한조 대기 중 (0) | 2025.05.14 |
