BOJ 백준 15271 친구 팰린드롬 2

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

 

[ 문제 요약 ]

• 주어진 그래프에서 **출석 번호가 짝수인 사람(남자)**과 **홀수인 사람(여자)**만 서로 연결될 수 있습니다. 이때 최대한 많은 남녀 쌍을 매칭하고, 매칭되지 않은 사람의 수를 최소화하는 것이 목표입니다.

 

[ 테스트 케이스 설명 ]

3 3	// 사람수(2<=200), 관계도 수(0<=(N^2 - N)/2)
1 2	// 친한 친구 관계가 주어짐
2 3
3 1
답 : 3

 

 

[ 알고리즘 분류 ]

• 이분 매칭

 

[ 문제 해설 ]

 

문제 설명에서 남, 여만 짝이 가능하다 하였으므로, 남,녀일 때, 남자 → 여자로 갈 수 있게 만들어 줍니다.

 

그리고 모든 사람에 대해서 탐색합니다. 이때 모든 사람에 대해 탐색해도, 여자는 남자로 갈 수 없으므로 자연히 남자만 탐색되게 되므로 모든 남녀 매칭을 해줄 수 있습니다.

 

한 번의 dfs에서 남,여로 두 명의 사람을 매칭하기 때문에 매칭된 사람의 수를 더할 때 2씩 증가시켜 줍니다.

 

무한 루프를 방지하기 위해 dfs 함수안에서 방문하지 않은 여자만 탐색하도록 합니다.

 

정답 출력 시 구한 cnt에 +1을 해주어야 합니다. 모두 매칭되지 않은 경우 한 명은 주최자로 추가하여 무대에 오르는 사람의 수를 최대로 합니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
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());// 사람수(2<=200)
		M = Integer.parseInt(st.nextToken());// 관계도 수(0<=(N^2 - N)/2)
		match = new int[N + 1];
		visit = new boolean[N + 1];
		adList = new ArrayList[N + 1];
		
		for(int i=0; i<=N; i++)
			adList[i] = new ArrayList<>();
		
		for(int i=0; i<M; i++)
		{
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(a % 2 != b % 2)
			{
				if(a % 2 == 0) // 남 -> 여로 갈 수 있게 세팅
					adList[a].add(b);
				else
					adList[b].add(a);
			}
		}
	
		int cnt = 0;
		
		for(int i=1; i<=N; i++)
		{
			Arrays.fill(visit, false);
			if(dfs(i))
				cnt += 2;
		}
		
		System.out.print(Math.min(cnt + 1, N));
	}
	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;
	}
}