kyjdummy 님의 블로그

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

[ 문제 요약 ]

• 정점 개수와 각 정점에 연결된 다른 정점들이 주어질 때, 주어지는 루트 노드 번호부터 깊이 우선 탐색을 하여 방문하는 인덱스를 출력하는 문제입니다.
• 깊이 우선 탐색 시 방문할 노드가 여러 개라면 노드 번호가 작은 순으로 방문합니다.

[ 테스트 케이스 설명 ]

3// 정점 수 (2<=100,000)
2 1 3 -1 // 정점 번호가 먼저 주어지고, -1입력 전까지 해당 정점에 연결된 노드가 주어진다.
3 2 -1
1 2 -1
2// 루트노드 번호
출력 : 루트노드 부터 탐색을 시작하여 번호가 가장 낮은 노드부터 오름차순 방문해서 중첩 집합을 구성할 때, 각 노드의 번호 left 필드와 right 필드 출력
1 2 3// 정점 수 만큼 LEFT필드와 RIGHT필드를 출력
2 1 6
3 4 5

[ 알고리즘 분류 ]

• 그래프 이론
• 그래프 탐색
• 트리
• 깊이 우선 탐색
• 오일러 경로 테크닉

[ 문제 해설 ]

간단한 오일러 경로 테크닉 문제로 몇 가지만 신경 써주면 간단히 풀 수 있습니다.

인접 노드를 저장할 때 작은 노드부터 방문해야 하기 때문에 노드정보 저장 시마다 노드를 오름차순으로 정렬해 줍니다.

그 후 방문할 때 전역 변수를 하나 두고, in, out 시마다 고유번호로 마킹해주면 됩니다.

출력은 1번 노드부터 N 번 노드 순으로 출력해 주면 됩니다.

[ 정답 코드 ]

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

class Main{
	
	static int N;
	static int idx;
	static int order[][];
	static int adNode[][];
	
	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());
		order = new int[N + 1][2];
		adNode = new int[N + 1][];
		
		for(int i=0; i<N; i++)
		{
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int len = st.countTokens() - 1;
			adNode[a] = new int[len];
			
			for(int j=0; j<len; j++)
				adNode[a][j] = Integer.parseInt(st.nextToken());
			
			Arrays.sort(adNode[a]);
		}
		
		dfs(Integer.parseInt(br.readLine()), 0);
		
		StringBuilder sb = new StringBuilder();
		
		for(int i=1; i<=N; i++)
			sb.append(i).append(' ').append(order[i][0])
				.append(' ').append(order[i][1]).append('\n');
		
		System.out.print(sb);
	}
	static void dfs(int now, int parent)
	{
		order[now][0] = ++idx;
		
		for(int next : adNode[now])
			if(next != parent)
				dfs(next, now);
		
		order[now][1] = ++idx;
	}
}

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

[ 문제 요약 ]

• 그래프가 주어질 때 단절점의 개수와 단절점의 번호를 오름차순으로 출력합니다. 주어지는 그래프는 연결 그래프가 아닐 수 있습니다.
• 단절점이란 해당 정점 제거 시 그래프가 두 개 또는 그 이상으로 나눠지는 정점을 의미합니다.

[ 테스트 케이스 설명 ]

7 7 // 1번부터 번호가 있는 정점의 수(1<=10,000), 간선수(1<=100,000)
1 4 // 간선 수 만큼 연결된 두 정점 A,B가 주어진다.
4 5
5 1
1 6
6 7
2 7
7 3
첫째 줄에 단절점의 개수 출력, 둘째 줄에는 단절점의 번호를 오름차순으로 출력
3
1 6 7

[ 알고리즘 분류 ]

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 단절점과 단절선

[ 문제 해설 ]

그래프에서 정점이 단절점인지 파악하는 방법은 간단한 몇 가지 규칙으로 알 수 있습니다.

1 ) 임의의 정점을 루트로 dfs 탐색을 하며 방문 순서를 순서대로 저장합니다.(그래프가 여러 컴포넌트라면, 방문하지 않은 정점마다 DFS를 다시 시작합니다.)

2 ) 각 정점마다 자기의 자식 노드가 자기 상위 노드로 갈 수 있는지를 체크합니다. 이때, 자기를 거치지 않고 가야 합니다. 만약 갈 수 없다면 자기가 없어졌을 때 자기 자식 노드와 자기 상위 노드가 끊어지므로 자기가 단절점이 됨을 알 수 있습니다.

3 ) 루트 노드 같은 경우 단절점 파악은 예외 처리해 줍니다. 루트 노드는 자식 노드가 2개 이상일 경우 무조건 단절점으로 둡니다.

구현할 때, 위 1번은 그냥 한 번의 dfs로 방문 순서를 담는 order 배열을 두어 처리할 수 있으나, 2번을 구현하는 게 어려울 수 있습니다. dfs 함수가 반환하는 값을, 자기 자식 노드가 방문할 수 있는 가장 앞선 방문 노드 번호를 반환하도록 하면 됩니다.

그리고 루트 노드의 경우 자식 노드가 2개 이상인지 파악하는 것은 정점에 연결된 다른 정점 개수로 파악하면 안됩니다. dfs 탐색 시 방문하는 실제 자식 노드 수를 카운팅 해야만 합니다. 아래와 같은 그래프 구조가 있을 때 1번의 인접 노드는 2개(4번과 2번)이지만, dfs 탐색 시 자식 노드는 1개뿐인 겁니다.

1

| \

4 2

| /

3

1 → 2 → 3 → 4 → 1로 방문하면, 1번의 자식 노드는 2번 하나뿐입니다.

[ 정답 코드 ]

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

class Main{
	
	static int N, E;
	static int idx, cutSize;
	static int order[];
	static boolean cut[];
	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());
		
		N		= Integer.parseInt(st.nextToken());// 1번부터 번호가 있는 정점의 수(1<=10,000)
		E		= Integer.parseInt(st.nextToken());// 간선수(1<=100,000)
		order	= new int[N + 1];
		cut		= 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<E; i++)
		{
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adList[a].add(b);
			adList[b].add(a);
		}
		
		for(int i=1; i<=N; i++)
		{
			if(order[i] == 0) // 아직 방문하지 않은 정점인 경우, 해당 정점을 루트노드로 탐색
			{
				dfs(i, 0);
			}
		}

		StringBuilder sb = new StringBuilder();
		
		sb.append(cutSize).append('\n');
		
		for(int i=1; i<=N; i++)
			if(cut[i])
				sb.append(i).append(' ');
		
		System.out.print(sb);
	}
	static int dfs(int now, int parent)
	{
		int min = order[now] = ++idx;
		int childCnt = 0;
		for(int next : adList[now])
		{
			if(next == parent)// 부모노드일 경우 스킵
				continue;
			
			if(order[next] > 0)
			{
				// 이미 방문한 정점(조상)으로 가는 간선
				min = Math.min(min, order[next]);
				continue;
			}
			childCnt++;
			// 자기 자식노드 중 갈 수 있는 low의 가장 작은 값 반환
			int low = dfs(next, now);
			
			// 자기 자식노드중 어떤 하나가 나보다 위로 못가면 내가 없어지면 단절점이 되는것
			// 다만 루트노드인 경우는 다른 조건으로 체크하기 위해 parent != 0 조건 추가
			if(parent != 0 && low >= order[now])
				cut[now] = true;
			
			min = Math.min(min, low);
			
		}
		// 루트노드는 자식노드가 2개이상일 때 무조건 단절점
		if(parent == 0 && childCnt >= 2)
			cut[now] = true;
		// 단절점 체킹 후 단절점 개수 추가
		if(cut[now])
			++cutSize;
		
		return min;
	}
}

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

[ 문제 요약 ]

• 그래프에서 체인이란 연속된 두 정점을 연결하는 간선이 존재하는 정점들의 나열입니다.
• 한 정점이 여러 번 등장할 수 있고, 정점 하나도 체인입니다.
• 사이클이 없는 방향 그래프가 주어질 때, 모든 정점을 포함시키기 위해 최소 몇 개의 체인이 필요한지 출력합니다.

[ 테스트 케이스 설명 ]

7 11// 정점 개수 (1<=10,000), 간선 개수(0<=100,000)
1 2// u, v가 주어지며 u에서 v로 가는 간선이라는 의미
1 5
2 5
2 3
2 7
3 4
3 6
4 6
5 4
5 6
7 3
그래프의 모든 정점을 포함시키기 위해 필요한 체인 개수의 최솟값 : 2

[ 알고리즘 분류 ]

• 이분 매칭

[ 문제 해설 ]

최소 개수의 체인으로 모든 정점을 커버하는 문제로,

방문 그래프가 주어졌을 때, 모든 정점을 포함하는 경로(체인)의 최소 개수를 구해야 합니다.

최소 경로 커버(Minimum Path Cover) : 방향 비순환 그래프(DAG)에서 모든 정점을 포함하는 서로 겹치지 않는 경로들의 집합 중 최소 개수를 구하는 것을 최소 경로 커버라 합니다.

DAG에서 최소 경로 커버 수를 구할 수 있는 공식은 아래와 같습니다.

DAG에서의 최소 경로 커버 수 = 전체 정점 수 - 이분 그래프에서의 최대 매칭 수

즉, 그래프에서 최대 매칭을 구해, 전체 정점과 빼주면 해당 문제의 답이 됩니다.

[ 정답 코드 ]

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

class Main{

	static int N, M;
	static int time;
	static int match[];
	static int visitTime[];
	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());
		N = Integer.parseInt(st.nextToken());// 정점 개수 (1<=10,000)
		M = Integer.parseInt(st.nextToken());// 간선 개수(0<=100,000)
		match = new int[N + 1];
		visitTime = new int[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 u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			adList[u].add(v);
		}
		
		int cnt = 0;
		for(int i=1; i<=N; i++)
		{
			++time;
			if(dfs(i))
				++cnt;
		}
		System.out.print(N - cnt);
	}
	static boolean dfs(int now)
	{
		for(int next : adList[now])
		{
			if(visitTime[next] == time)
				continue;
			
			visitTime[next] = time;
			if(match[next] == 0 || dfs(match[next]))
			{
				match[next] = now;
				return true;
			}
		}
		return false;
	}
}

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

[ 문제 요약 ]

• 나무 막대들이 주어지고, 나무 막대로 삼각형을 만들 때 만들 수 있는 최대 수를 출력합니다.
• 삼각형은 직각 삼각형만 해당하며, 빗변으로 사용할 쇠막대는 길이 무한, 개수 무한이기 때문에 신경 쓰지 않아도 됩니다.
• 빗변을 제외한 두변을 나무 막대로 만들 때 만들 수 있는 최대 수를 출력합니다.
• 빗변을 제외한 두변의 최대 공약수는 1이어야 합니다.

[ 테스트 케이스 설명 ]

9// 나무 막대 개수(1<=200)
3 4 4 3 11 5 12 9 4// 나무막대 길이(1<=1,000,000)
만들 수 있는 장난감의 최대수 : 3

[ 알고리즘 분류 ]

• 수학
• 정수론
• 이분 매칭

[ 문제 해설 ]

직각삼각형을 만들 때, 빗변을 제외한 나머지 두 변을 나무 막대로 만들 때, 두 나무 막대 길이의 최대 공약수가 1이라는 것은 두 나무막대 길이가 서로소인 숫자들만 매칭이 가능하다는 것을 의미합니다.

두수가 서로소이면서, 두 숫자를 통해 도출할 빗변의 길이가 완전 제곱수이여야 합니다. 두 숫자를 고르는 방법은 아래와 같이 3가지 방법이 있습니다.

짝수 + 짝수

홀수 + 홀수

짝수 + 홀수

위 3가지 방법 중, 짝수 2개를 고르게 되면 최대 공약수가 1이 아니기 때문에 불가합니다. 홀수 + 홀수로 하게 되면 두 숫자로 만든 빗변의 길이가 완전 제곱수가 아니기 때문에 홀수 2개 선택도 불가합니다.

결국 짝수 + 홀수만 문제 조건을 만족하기 때문에 각 숫자들을 짝, 홀로 구분하여 그래프를 모델링하고 조건에 따라 간선을 만들어 이분 매칭으로 답을 출력하면 됩니다.

두 나무막대가 주어질 때, 두 숫자가 서로소라 할지라도, 빗변의 값이 완전 제곱수가 아닌 경우는 직각 삼각형을 만들 수 없어 완접 제곱수 파악을 필수로 해주어야 합니다.

[ 가능한 완전 제곱수 예시 설명 ]

• a = 3, b = 4 일 때, 두 숫자는 서로소이고, 피타고라스 정리에 의해 도출한 빗변의 길이도 3 * 3 + 4 * 4 = 25로 완전 제곱수입니다.

[ 불가능한 완전 제곱수 예시 설명 ]

• a = 2, b = 3일 때, 두 숫자는 서로소이지만, 피타고라스 정리에 의해 도출된 빗변의 길이는 2 * 2 + 3 * 3 = 13이므로 완전 제곱수가 아닙니다.

[ 정답 코드 ]

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

class Main{
	
	static int N;
	static int time;
	static int match[];
	static int visitTime[];
	static List<Integer> adList[];
	static List<Integer> even;
	static List<Integer> odd;
	
	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());
		match = new int[N + 1];
		visitTime = new int[N + 1];
		adList = new ArrayList[N + 1];
		even = new ArrayList<>();
		odd = new ArrayList<>();
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
		{
			int num = Integer.parseInt(st.nextToken());
			if(num % 2 == 0)
				even.add(num);
			else
				odd.add(num);
			
			adList[i] = new ArrayList<>();
		}
		
		for(int i=0; i<even.size(); i++)
		{
			int e = even.get(i);
			for(int j=0; j<odd.size(); j++)
			{
				int o = odd.get(j);
				// 최대 공약수가 1이면서, 완전 제곱수인 경우만 간선을 연결
				if(gcd(e, o) == 1 && isSqure((long)e * e + (long)o * o))
					adList[i + 1].add(j + 1);
			}
		}
		
		int cnt = 0;
		
		for(int i=1; i<=even.size(); i++)
		{
			++time;
			
			if(dfs(i))
				++cnt;
		}
		
		System.out.print(cnt);
	}
	static boolean dfs(int i)
	{
		for(int j : adList[i])
		{
			if(visitTime[j] == time)
				continue;
			
			visitTime[j] = time;
			
			if(match[j] == 0 || dfs(match[j]))
			{
				match[j] = i;
				return true;
			}
		}
		return false;
	}
	static boolean isSqure(long x) {
		long sq = (int)Math.sqrt(x);
		return x == sq*sq;
	}
	static int gcd(int a, int b) {
		if(b == 0) return a;
		return gcd(b, a % b);
	}
}

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

[ 문제 요약 ]

• 뽁뽁이는 N 개의 색상이 있고, 꼭꼭이는 M 개의 색상이 있습니다. K 명의 친구들에게 다음과 같은 질문을 던집니다. 질문 : 사고 싶은 뽁뽁이 색상과 사고 싶지 않은 꼭꼭이 모델을 하나씩 고르거나, 그 반대로 사고 싶지 않은 뽁뽁이 생상과 사고 싶은 꼭꼭이 모델을 하나씩 고르시오.
• 욱제는 최대한 많은 친구들을 만족시키고 싶어 한다. 친구들은 자신의 두 요구사항이 모두 반영되어야 만족합니다.
• 만족하지 못하게 되는 친구들에게 사탕을 하나씩 주려고 한다. 욱제는 최소 몇 개의 사탕을 준비해야 할지 출력합니다.

[ 테스트 케이스 설명 ]

2 3 5 // 뽁뽁이 색상 수N(1<=128), 꼭꼭이 색상 수 M(1<=128), 친구들의 수 K(1<=512)
1 3 0// K줄에 걸쳐 ni, mi, ci가 주어지며 ni은 뽁뽁이, mi 꼭꼭이 모델이며 ci가 0이면 ni를 구매, 1이면 mi를 구매하길 원하는것
2 3 0
2 2 1
2 1 0
1 3 1
최소 준비해야하는 사탕 수 : 2

[ 알고리즘 분류 ]

• 이분 매칭

[ 문제 해설 ]

그래프 모델링이 중요한 문제입니다. 그래프 모델링 후 단순히 이분 매칭의 최대 크기만 구하면 됩니다.

그래프 모델링 시 i 번 사람이 (1) 뽁뽁이를 원하고, (2)꾹꾹이를 싫어하고, i+1번 사람이 (2)꾹꾹이를 원하고, (1) 뽁뽁이를 싫어한다면?

그러면 i 번째 사람과 i + 1번째 사람은 서로 상반되기 때문에 그래프 간선을 연결해 줍니다.

정리하면 내가 사려는 것을 상대가 싫어한다면 간선을 연결해 줍니다.

사탕을 받는 사람은 선택받지 못한 사람 수이기 때문에 불가능한 노드끼리 연결하여 최소 정점 커버 크기를 출력해 주면 됩니다.

그냥 간선을 연결한다면 이분 그래프가 아니기 때문에 입력되는 ci 값에 따라 인접 노드를 저장하는 인덱스를 달리해서 저장해야 합니다.

[ 정답 코드 ]

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

class Main{
	
	static int N, M, K;
	static List<Node> pre;
	
	static int time;
	static int match[];
	static int visitTime[];
	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());
		N = Integer.parseInt(st.nextToken());// 뽁뽁이 색상 수N(1<=128)
		M = Integer.parseInt(st.nextToken());// 꼭꼭이 색상 수 M(1<=128)
		K = Integer.parseInt(st.nextToken());// 친구들의 수 K(1<=512)
		pre = new ArrayList<>();
		match = new int[K + 1];
		visitTime = new int[K + 1];
		adList = new ArrayList[K + 1];
		
		for(int i=0; i<=K; i++)
		{
			adList[i] = new ArrayList<>();
			match[i] = -1;
		}

		for(int i=0; i<K; i++)
		{
			st = new StringTokenizer(br.readLine());
			int ni = Integer.parseInt(st.nextToken());
			int mi = Integer.parseInt(st.nextToken());
			int ci = Integer.parseInt(st.nextToken());
			
			pre.add(new Node(ni, mi, ci));
		}
		
		for(int i=0; i<K; i++)
		{
			Node l = pre.get(i);
			for(int j=i + 1; j<K; j++)
			{
				Node r = pre.get(j);
				
				if(
					(l.ni == r.ni || l.mi == r.mi) && l.ci != r.ci
					)
				{
					if(l.ci == 1)
						adList[i].add(j);
					else
						adList[j].add(i);
				}
			}
		}
		
		int cnt = 0;
		
		for(int i=0; i<K; i++)
		{
			++time;
			if(dfs(i))
				++cnt;
		}
		
		System.out.print(cnt);
	}
	static boolean dfs(int a)
	{
		for(int b : adList[a])
		{
			if(visitTime[b] == time)
				continue;
			
			visitTime[b] = time;
			
			if(match[b] == -1 || dfs(match[b]))
			{
				match[b] = a;
				return true;
			}
		}
		return false;
	}
	static class Node{
		int ni, mi, ci;
		Node(int n, int m, int c){
			ni = n;
			mi = m;
			ci = c;
		}
	}
}

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

[ 문제 요약 ]

• N, M 크기 체스판이 주어지고, 몇몇 칸엔 X 표시가 있습니다. 게임은 두 명이 번갈아 가며 진행되며 아래 규칙을 따릅니다
• 규칙 1 : 아직 선택되지 않은 행 또는 열을 하나 선택하되, 기존에 선택되었던 행과 열과의 교차점에 X가 없어야 함
• 규칙 2 : 선택 후 상대 차례가 됨
• 규칙 3 : 조건을 만족하는 행 or 열이 없다면 그 사람이 지고 게임이 끝난다.
• 해당 규칙을 따라 게임을 진행할 때, 최대 몇 번의 선택을 할 수 있는지 출력합니다.

[ 테스트 케이스 설명 ]

4 4 6// N(1<=200), M(1<=200), X 표시된 칸의 수 K(1<=N*M)
1 1//K줄에 걸쳐 두 자연수 X가 있는 좌표 X(1 ≤ N),Y(1 ≤ M)가 주어짐( 좌표 중복은 없음 )
1 3
2 4
3 2
3 4
4 3
//총 몇번의 선택이 가능한지 : 4

[ 알고리즘 분류 ]

• 이분 매칭

[ 문제 해설 ]

이 문제는 최대 독립 집합을 구하는 간단한 문제입니다.

독립 집합 : 모든 정점의 집합 U가 있을 때, 그 부분 집합 V 안에서 어떤 두 개의 정점을 선택해도 서로 간선이 없는 것을 의미

최대 독립 집합 : 독립 집합의 크기가 가장 큰것

최대 독립 집합의 크기 : 모든 노드 수 - 최소 정점 커버

최소 정점 커버 : 이분 그래프일 때, 이분 매칭의 최대 크기와 같음(쾨닉의 정리)

최대 독립 집합은, 정점 집합에서 어떤 두 노드를 선택해도 서로 간선이 없는 것을 의미합니다. 이 문제에서 요구하는 것입니다. 가로 세로가 겹칠 때, X가 없어야 합니다.

한쪽은 가로 값, 한쪽은 세로 값을 갖는 이분 그래프라 생각하고 X 표시가 간선을 의미하도록 하여 그래프를 생성해 줍니다.

이렇게 생성한 그래프는 이분 그래프가 되고, 최대 매칭을 구해서 모든 노드 수에서 빼면 최대 독립 집합의 수가 됩니다.

정리하면, 문제 상황을 최대 독립 집합 크기로 구할 수 있도록 그래프를 모델링하고 공식에 의해 답을 도출하는 것입니다.

여기서 모든 노드는 가로행 수와, 세로 행수의 합이 됩니다. 그래프의 노드는 한쪽은 가로, 한쪽은 세로 값이 되며 간선은 X좌표일 때만 연결합니다.

[ 정답 코드 ]

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

class Main{
	
	static int N, M, K;
	static List<Integer> adList[];
	
	static int time;
	static int match[];
	static int visitTime[];
	
	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());// N(1<=200)
		M = Integer.parseInt(st.nextToken());// M(1<=200)
		K = Integer.parseInt(st.nextToken());// X 표시된 칸의 수 K(1<=N*M)
		adList = new ArrayList[N + 1];
		match = new int[M + 1];
		visitTime = new int[M + 1];
		
		for(int i=0; i<=N; i++)
			adList[i] = new ArrayList<>();
		
		for(int i=0; i<K; i++)
		{
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			adList[x].add(y);
		}
		
		int cnt = 0;
		
		for(int x=1; x<=N; x++)
		{
			++time;
			if(dfs(x))
				++cnt;
		}
		System.out.print(N + M - cnt);
	}
	static boolean dfs(int x)
	{
		for(int y : adList[x])
		{
			if(visitTime[y] == time)
				continue;
			
			visitTime[y] = time;
			
			if(match[y] == 0 || dfs(match[y]))
			{
				match[y] = x;
				return true;
			}
		}
		return false;
	}
}

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

[ 문제 요약 ]

• A에는 정점이 1번부터 N 번까지 있고, B에는 정점이 1번부터 M까지 있습니다.
• A의 i 번 정점은 Ai로, B의 j 번 정점은 Bj로 표시합니다. 이 그래프의 최소 버텍스 커버를 구하는 프로그램을 작성합니다.
• 버텍스 커버란 정점의 집합으로 주어진 그래프에서 버텍스 커버에 포함된 정점들을 제거하면 간선이 하나도 없는 집합을 말합니다.
• 최소 버텍스 커버는 이 집합들 중 크기(정점의 개수)가 최소인 것을 말합니다. 그래프에서 정점을 제거할 때는, 그 정점에 연결된 모든 간선도 함께 제거하게 됩니다.

[ 테스트 케이스 설명 ]

5 5 // N, M(1<=N,M<=1,000)
2 1 2// N개의 줄에 Ai와 연결된 정점의 개수가 주어지고 그 개수만큼 Bj의 j가 주어짐
1 1
2 2 3
3 3 4 5
1 1
출력은 첫 줄에 최소 버텍스 커버 크기를 출력하고, 둘째 줄은 A에서 최소 버텍스 커버에 포함되어 있는 정점의 개수를 출력, 포함되어 있는 정점 번호(Ai에서 i)를 출력
셋째 줄엔 B에서 최소 버텍스 커버에 포함되어 있는 정점의 개수를 출력하고, 포함되어 있는 정점의 번호(Bj에서 j)를 출력
4
2 3 4
2 1 2

[ 알고리즘 분류 ]

• 그래프 이론
• 이분 매칭

[ 문제 해설 ]

이분 그래프에서 단순 최소 정점 커버 크기를 구하는 것은 이분 매칭으로 간단히 구할 수 있습니다. 그러나 해당 정점들을 출력하는 것은 별도의 공식이 필요합니다.

공식 : K = (A / Z) ∪ ( B ∩ Z )

아래는 위 공식을 이해하기 위한 개념 정리입니다.

교대 경로 : 비매칭 간선 -> 매칭 간선 -> 비매칭 간선 -> 매칭 간선 ... 식으로 번갈아 이어지는 경로

K : 최소 정점 커버(Vertex Cover) – 그래프의 모든 간선을 가리는 가장 작은 정점 집합( 모든 간선을 최소 개수의 정점으로 가리는 집합 )

A : 왼쪽 파트의 정점 집합

B : 오른쪽 파트의 정점 집합

Z : 최대 매칭이 주어졌을 때, 매칭이 안된 왼쪽 정점에서 교대 경로로 도달 가능한 정접의 집합( 다른 말로 하면, 자유 (Free) 왼쪽 정점에서 교대 경로를 따라 도달 가능한 왼쪽·오른쪽 모든 정점의 집합)

A / Z : A에서 Z를 빼고 남은 것(차집합)

B ∩ Z : B와 Z의 공통부분(교집합)

∪ : 두 집합을 합친 것(합집합)

최대 매칭이 주어질 때 K = (A / Z) ∪ ( B ∩ Z ) 공식이 성립함.

교대 경로 Z를 만들 때 방문하는 노드를 모두 기록하면 그게 해당 문제의 답이 됩니다.

먼저 입력으로 각 노드의 번호가 주어지므로 위 공식에 나오는 A와 B는 알 수 있습니다. 그리고 이분 매칭을 통해 A 쪽에 매칭이 되지 않은 노드들도 알 수 있습니다. A 쪽에 매칭이 되지 않은 노드들을 기준으로 교대 경로를 탐색합니다. 교대 경로 탐색 과정에서 방문하는 A와 B 쪽 노드들을 마킹하면, K = (A / Z) ∪ ( B ∩ Z ) 공식에 의해, A에서는 방문하지 않은 노드들이 정답이 되고(차집합이니까) B는 방문한 정점들이 정답이 됩니다.(교집합이니까)

여기서 중요한 것은 교대 경로를 탐색하는 재귀 함수를 만드는 데 있습니다. A를 왼쪽 정점 집합이라 칭하고, B를 오른쪽 정점이라 칭할 때, A는 매칭에 포함되지 않은 간선만 따라가고, B는 매칭에 포함된 간선만 따라가게 만들면, 비매칭 → 매칭 → 비매칭 → 매칭 노드들만 방문하게 됩니다. 이때, 방문한 노드들이 답이 되는데 비매칭만 따라간 A 쪽 집합은 방문하지 않은 정점들만 답이 됩니다.(위 공식에서 차집합이라 했으니까.)

	// 매칭에 포함되지 않은 Left 정점에서 교대 경로 Z를 탐색하기 위해 DFS로 재귀탐색한다.
	// - Left → Right : 매칭에 포함되지 않은 간선만
	// - Right → Left : 매칭에 포함된 간선만
	// 최소 버텍스 커버 = (A \ Z) ∪ (B ∩ Z)
	static void dfs(int left)
	{
		if(visitLeft[left])// left 이미 방문시 연산 스킵
			return;
		// left 방문 처리
		visitLeft[left] = true;
		// 미매칭 정점(left)의 인접 노드들(right) 탐색
		for(int right : adList[left])
		{
			// left와 이미 매칭되어 있거나, 인접 노드가 이미 방문했다면 연산 스킵
			if(match[right] == left || visitRight[right])
				continue;
			// 인접 노드 방문 처리
			visitRight[right] = true;
			// right와 매칭된 노드가 있다면 해당 노드로 다시 dfs
			if(match[right] != 0)
				dfs(match[right]);
		}
	}

[ 정답 코드 ]

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

class Main{
	
	static int L, R;
	static int time;
	static int visitTime[];
	static int match[];
	static int reverseMatch[];
	static List<Integer> adList[];
	
	static boolean visitLeft[];
	static boolean visitRight[];
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		L = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		visitTime = new int[R + 1];
		match = new int[R + 1];
		reverseMatch = new int[L + 1];// 왼쪽 노드의 미매칭 상황을 알기위해 필요하다.
		adList = new ArrayList[L + 1];
		visitLeft = new boolean[L + 1];
		visitRight = new boolean[R + 1];
		
		for(int i=0; i<=L; i++)
			adList[i] = new ArrayList<>();
		// 간선을 입력 받는다
		for(int l=1; l<=L; l++)
		{
			st = new StringTokenizer(br.readLine());
			int cnt = Integer.parseInt(st.nextToken());
			while(cnt-->0)
				adList[l].add(Integer.parseInt(st.nextToken()));
		}
		
		int cnt = 0;
		// 왼쪽 정점 기준으로 이분 매칭을 돌려서 크기를 구함과 동시에 매칭된 노드들을 서로 저장한다.
		for(int l=1; l<=L; l++)
		{
			++time;
			if(bipartite(l))
				++cnt;
		}
		// 왼쪽 정점 그룹 기준으로 미매칭 노드를 시작으로 교대 경로를 탐색한다. 왼쪽 정점은 매칭되지 않은 것만, 오른쪽 정점은 매칭된것만 탐색한다.
		// dfs 함수안에서 탐색하는 모든 정점들을 방문 체크하여 어떤 노드를 방문했는지 알 수 있도록 한다.
		for(int l=1; l<=L; l++)
			if(reverseMatch[l] == 0)// 왼쪽 노드 기준, 미매칭 인것들을 기준으로 dfs 탐색
				dfs(l);
		
		StringBuilder sb = new StringBuilder();
		sb
		.append(cnt).append('\n')
		.append(getAns(visitLeft, false))// 왼쪽 정점은 차집합이기 때문에 방문하지 않은 정점을 답으로 출력
		.append('\n')
		.append(getAns(visitRight, true));// 오른쪽 정점은 교집합이기 때문에 방문한 정점을 답으로 출력
		
		System.out.print(sb);
	}
	static String getAns(boolean visit[], boolean flag) {
		StringBuilder sb = new StringBuilder();
		int cnt = 0;
		for(int i=1; i<visit.length; i++)
		{
			if(visit[i] == flag)// 전달된 flag와 같을 때만 답으로 출력
			{
				++cnt;
				sb.append(i).append(' ');
			}
		}
		sb.insert(0, ' ');
		sb.insert(0, cnt);// 맨처음 값이 정점의 개수여야 하므로 insert 처리
		
		return sb.toString();
	}
	static void dfs(int left) {
		if(visitLeft[left])// 왼쪽 정점 방문했다면 연산 스킵
			return;
		// 왼쪽 정점 방문 처리
		visitLeft[left] = true;
		// 왼쪽 정점은 미매칭 간선만 탐색, 오른쪽 정점은 매칭만 탐색하도록 하여 비매칭 -> 매칭 -> 비매칭 -> 매칭 으로 교대 간선 탐색하도록 구현
		for(int right : adList[left])
		{
			// 오른쪽 정점을 방문했거나, 오른쪽 정점이 왼쪽 정점과 매칭되있다면 연산 스킵한다.
			if(visitRight[right] || match[right] == left)
				continue;
			// 오른쪽 정점 방문 처리
			visitRight[right] = true;
			// 재귀 탐색
			if(match[right] != 0)
				dfs(match[right]);
		}
	}
	static boolean bipartite(int left) {
		for(int right : adList[left])
		{
			if(visitTime[right] == time)
				continue;
			
			visitTime[right] = time;
			
			if(match[right] == 0 || bipartite(match[right]))
			{
				match[right] = left;
				reverseMatch[left] = right;// 미매칭 노드 파악을 위해 필요하다.
				return true;
			}
		}
		return false;
	}
}

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

[ 문제 요약 ]

• N 명의 용의자가 주어집니다. 각 용의자에게는 2명의 친구가 주어집니다.
• 친구 한 명은 용의자 1명만 변호할 수 있으며, 자기가 만족하는 비용 이상인 경우 해당 용의자의 변호인이 되어줍니다.
• 같은 친구라도, 용의자에 따라 만족 비용이 다를 수 있습니다.
• 용의자의 수와, 1명의 용의자가 갖는 두 명의 친구 번호 + 만족 비용이 주어질 때 모든 용의자가 1명 이상의 변호인을 둘 수 있는 최소 파티 비용 K를 출력합니다. 없다면 -1을 출력합니다.

[ 테스트 케이스 설명 ]

3// 용의자 수(1<=200,000)
1 5 2 6// 용의자 수만큼, i번째 용의자의 친구를 나타내는 정수 Ai와 해당 친구를 변호인으로 두기 위한 임계값 KAi, 다른 친구정수 Bi와 해당 친구를 변호인으로 두기위한 KBi가주어짐(친구번호 : 1<=2*용의자수 / 임계값은 0<=백만)
2 7 3 8
3 9 1 10
모든 용의자가 변호인을 갖게 되는 파티의 최소 비용K 출력 및 없으면 -1출력
답 : 9

[ 알고리즘 분류 ]

• 그래프 이론
• 이분 탐색
• 이분 매칭
• 강한 연결 요소
• 2-SAT

[ 문제 해설 ]

이 문제는 단순한 이분 매칭 + 이분 탐색 문제입니다.

K의 값을 이분 탐색하고, 특정 K 값일 때, 모든 용의자가 매칭되는지만 판단하면 됩니다.

각 친구마다 원하는 비용이 있으므로 인접 리스트를 만들 때 별도의 자료구조가 필요합니다.

각 친구 번호마다 자기가 원하는 비용(cost)를 갖고 있도록 하고, 이분 매칭을 돌릴 때 K가 원하는 비용 이상인 경우만 매칭을 탐색하도록 구현하면 간단히 해결 가능합니다.

이분 매칭을 여러 번 해야 하므로 배열 초기화를 최소화하기 위해 방문 체크를 boolean이 아니라 int형으로 하는 것이 유리합니다.

[ 정답 코드 ]

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 final int LEN = 400_000;
	static int N, K;
	static int time;
	static int visitTime[];
	static int match[];
	static List<Friend> adList[];
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		visitTime = new int[LEN + 1];
		match = new int[LEN + 1];
		adList = new ArrayList[N + 1];
		
		for(int i=1; i<=N; i++)
		{
			adList[i] = new ArrayList<>();
			st = new StringTokenizer(br.readLine());
			adList[i].add(new Friend(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
			adList[i].add(new Friend(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
		}
		// 이분 탐색으로 최소 K를 찾음 
		int res = -1;
		int s = 0;
		int e = 1_000_000;
		
		while(s <= e)
		{
			K = (s + e) >> 1;
			if(cal())
			{
				res = K;
				e = K - 1;
			}
			else
				s = K + 1;
		}
		
		System.out.print(res);
	}
	static boolean dfs(int suspect) {
		for(Friend f : adList[suspect])
		{
			if(f.cost <= K)// K가 친구가 원하는 비용보다 큰지 체크
			{
				// 비용을 만족하면 해당 친구 방문 체크 및 방문 처리
				if(visitTime[f.num] == time)
					continue;
				
				visitTime[f.num] = time;
				
				if(match[f.num] == 0 || dfs(match[f.num]))
				{
					match[f.num] = suspect;
					return true;
				}
			}
		}
		return false;
	}
	static boolean cal() {
		Arrays.fill(match, 0);
		
		int cnt = 0;
		
		for(int suspect=1; suspect<=N; suspect++)
		{
			++time;
			if(dfs(suspect))
				++cnt;
		}
		
		return cnt == N;
	}
	static class Friend{
		int num, cost;
		Friend(int n, int c){
			num = n;
			cost = c;
		}
	}
}

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

[ 문제 요약 ]

• 격자 판이 주어집니다. 왼쪽 위가 0,0부터 시작하고, 크기는 한 변이 최대 1,000입니다.
• 가로로 쓰는 단어와 세로로 쓰는 단어가 주어집니다. 격자판 하나에 단어들을 넣을 수 있습니다. 단어들의 시작 위치 x, y가 주어질 때, 단어들이 겹치지 않게 배치했을 때, 최대로 배치할 수 있는 단어의 수를 출력합니다.
• 가로 단어끼리 위치가 겹치거나, 세로 단어끼리 위치가 겹치는 경우는 없습니다.
• x는 가로 위치, y는 세로 위치를 의미합니다.
• 가로 단어는 오른쪽 방향으로, 세로 단어는 아래 방향으로 써 내려갑니다.

[ 테스트 케이스 설명 ]

2// 테스트케이스 
2 2// 가로 단어, 세로 단어 개수(1<=500)
0 1 BAPC// 가로 단어 수 만큼 각 가로 단어의 시작 위치 x,y와 답이라 생각하는 단어가 대문자로(W) 주어짐(0 ≤ x, y ≤ 1,000 이고 1 ≤ Length(W) ≤ 1,000)
0 2 LEIDEN
0 0 SOLUTION// 세로 단어 수 만큼 시작 위치 x,y와 답이라 생각하는 단어가 대문자로 주어짐(0 ≤ x, y ≤ 1,000 이고 1 ≤ Length(W) ≤ 1,000)
2 1 WINNER
1 4
0 1 HELLO
1 0 HI
2 0 BYE
3 0 GOODBYE
4 0 FAREWELL
//이하답
3
4

[ 알고리즘 분류 ]

• 이분 매칭

[ 문제 해설 ]

격자 판에 글자를 겹치지 않게 놓는 것은 최대 독립 집합 개념으로 구할 수 있습니다.

최대 독립 집합 : 모든 노드 집합 U가 있을 때, 특정 부분 집합 V 안에서 어떤 두 노드를 선택해도 연결된 간선이 하나도 없는 것을 의미합니다.

최소 정점 커버 : 모든 간선을 최소 개수의 정점으로 덮는 집합입니다.( 그래프가 이분 그래프일 때만 이분 매칭의 최대 매칭 크기와 같습니다.)

최대 독립 집합의 크기를 구하는 공식이 있습니다.

최대 독립 집합 = 총 노드 수 - 최소 정점 커버(이분 매칭 최대 크기)

문제를 최대 독립 집합을 구하는 것으로 치환하기 위해 아래와 같이 생각할 수 있습니다.

가로 글자끼리 겹치지 않고, 세로 글자끼리 겹치지 않는다 했지만, 가로와 세로는 겹칠 수 있으므로 겹치는 부분을 간선으로 만들면 가로, 세로끼리만 연결된 이분 그래프가 됩니다.

간선으로 만들 때, 서로 모순되는 부분만 간선으로 만들면 됩니다. 가로로 글자를 쓴 곳에 세로 글자가 덮어씌워질 때, 글자가 서로 맞지 않다면 해당 두 단어를 간선으로 연결해 줍니다.

그러면 그래프는 서로 양립할 수 없는 노드들끼리 연결되는 형태가 되고, 여기서 최소 정점 커버 수를(이분 매칭의 최대 크기) 구해서 총 노드 수와 빼주면 최대 독립 집합의 크기가 됩니다.

정리하면, 최대 독립 집합은 해당 집합 안에서 어떤 두 노드를 선택해도 연결된 간선이 없는 것이므로, 문제가 되는 부분을 일부러 간선으로 만들고, 이분 매칭으로 풀어내는 것입니다.

[ 정답 코드 ]

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

class Main{
	
	static int match[];
	static int visitTime[];
	static int time;
	static List<Integer> adList[];
	static char[][] map;
	static int[][] xIdx;
	static int X, Y;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		init();
		
		int T = Integer.parseInt(br.readLine());
		while(T-->0)
		{
			clear();
			
			st = new StringTokenizer(br.readLine());
			X = Integer.parseInt(st.nextToken());// 가로 단어(1<=500)
			Y = Integer.parseInt(st.nextToken());// 세로 단어 개수(1<=500)
			for(int i=0; i<X; i++)
			{
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				String word = st.nextToken();
				for(int j=0; j<word.length(); j++)
				{
					map[x + j][y] = word.charAt(j);
					xIdx[x + j][y] = i;
				}
			}
			for(int i=0; i<Y; i++)
			{
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				String word = st.nextToken();
				for(int j=0; j<word.length(); j++)
				{
					char c = word.charAt(j);
					if(map[x][y + j] != c && map[x][y + j] != 0)
						adList[xIdx[x][y + j]].add(i);
				}
			}
			
			int cnt = 0;
			for(int i=0; i<X; i++)
			{
				++time;
				if(dfs(i))
					++cnt;
			}
			
			sb.append(Y + X - cnt).append('\n');
			
		}
		System.out.print(sb);
	}
	static boolean dfs(int now) {
		for(int next : adList[now])
		{
			if(visitTime[next] == time)
				continue;
			
			visitTime[next] = time;
			
			if(match[next] == -1 || dfs(match[next]))
			{
				match[next] = now;
				return true;
			}
		}
		return false;
	}
	static void clear()
	{
		for(int i=0; i<match.length; i++)
		{
			match[i] = -1;
			adList[i].clear();
		}
		for(int y=0; y<=2000; y++)
			for(int x=0; x<=2000; x++)
				map[y][x] = 0;
	}
	static void init() {
		int len = 2001;
		match = new int[len];
		visitTime = new int[len];
		map = new char[len][len];
		adList = new ArrayList[len];
		xIdx = new int[len][len];
		for(int i=0; i<len; i++)
			adList[i] = new ArrayList<>();
	}
}

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

[ 문제 요약 ]

• 고양이와 개의 번호들이 주어집니다. 각 사람은 진출시킬 동물과 떨어뜨릴 동물을 한 마리씩 투표합니다.
• 모든 투표는 고양이 번호 하나와 개의 번호 하나로 이루어져 있습니다.
• 투표가 반영되면 계속 시청하고 그렇지 않으면 더 이상 시청하지 않습니다.
• 투표 반영이란, 다음 라운드에 진출하는 동물로 뽑은 동물이 다음 라운드에 진출하고, 현재 라운드에 탈락시키기로 한 동물이 탈락하는 것을 의미하며, 둘이 동시에 만족돼야 합니다.
• 각 시청자의 투표 결과가 주어질 때 다음 라운드를 시청할 시청자 수의 최댓값(투표가 반영되는 시청자의 최댓값)을 출력합니다.

[ 테스트 케이스 설명 ]

2 // 테스트 케이스 수 ( 1<=100 )
1 1 2	// 고양이 수(1<=100), 개의 수(1<=100), 투표한 시청자의 수(0<=500)
C1 D1// 시청자의 수 만큼 주어지며, 순서는 다음 라운드에 진출 시킬 동물, 탈락시킬 동물 이다. 고양이는 C로시작, 개는 D로시작하며 뒤 숫자는 동물의 번호다
D1 C1
1 2 4
C1 D1
C1 D1
C1 D2
D2 C1
각 테스트 케이스마다 투표가 반영되는 시청자의 최댓값을 출력
1
3

[ 알고리즘 분류 ]

• 이분 매칭

[ 문제 해설 ]

이 문제는 최대 독립 집합을 구하는 문제입니다.

최대 독립 집합 : 모든 노드 집합 V가 있을 때, 특정 부분 집합 U 안에서 어떤 두 노드를 선택해도 연결된 간선이 하나도 없는 것을 의미합니다.

최소 정점 커버 : 모든 간선을 최소 개수의 정점으로 덮는 집합입니다.( 그래프가 이분 그래프일 때만 이분 매칭의 최대 매칭 크기와 같습니다.)

누구는 고양이를 올리고 강아지를 떨어뜨리고, 누구는 강아지를 올리고 고양이를 떨어뜨릴 때, 서로 올리고 내리는 번호가 같다면 모순됩니다. 이러한 모순인 경우를 간선으로 만들어주고, 모순 간선이 하나도 없을 때, 그 집합의 크기가 답이 됩니다.

최대 독립 집합의 크기를 구하는 공식이 있습니다.

최대 독립 집합 = 총 노드 수 - 최소 정점 커버(이분 매칭 최대 크기)

여기서 총 노드는, 입력되는 V 즉, 투표하는 사람입니다. 각각의 투표마다, 고양이를 좋아하는 집합과 강아지를 좋아하는 집합을 list로 만들어 놓습니다. list로 만들어 놓는 이유는 추후 완전 탐색을 진행하며 모순되는 것을 찾아내고 이분 매칭에 사용할 간선을 만들어주기 위해서입니다.

모순되는 내용에 대해 간선 생성 후 단순히 이분 매칭으로 최소 정점 커버의 크기를 구합니다. 이분 매칭의 최대 크기는 최소 정점 커버의 크기를 의미합니다(쾨닉의 정리)

구한 값을 총 노드 수 V와 빼면 최대 독립 집합의 크기가 나오며 이 값이 답입니다

[ 정답 코드 ]

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

class Main{
	
	static int V;
	static int time;
	static int visitTime[];
	static int match[];
	static List<Integer> adList[];
	static List<Node> cat;
	static List<Node> dog;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		init();
		
		int T = Integer.parseInt(br.readLine());
		while(T-->0)
		{
			clear();
			
			st = new StringTokenizer(br.readLine());
			st.nextToken();// N은 버림
			st.nextToken();// M도 버림
			V = Integer.parseInt(st.nextToken());
			
			for(int i=0; i<V; i++)
			{
				st = new StringTokenizer(br.readLine());
				String a = st.nextToken();
				String b = st.nextToken();
				int num1 = Integer.parseInt(a.substring(1));
				int num2 = Integer.parseInt(b.substring(1));
				if(a.charAt(0) == 'C')// 고양이를 올릴 사람
					cat.add(new Node(num1, num2));
				else// 강아지를 올릴 사람
					dog.add(new Node(num1, num2));
			}
			
			// 서로 모순인 것을 간선으로 연결
			for(int i=0; i<cat.size(); i++)
			{
				Node c = cat.get(i);
				for(int j=0; j<dog.size(); j++)
				{
					Node d = dog.get(j);
					// 고양이를 올릴 사람과, 고양이를 떨어뜨릴 사람의 고양이 번호가 같으면 연결
					// 강아지를 올릴 사람과, 강아지를 떨어뜨릴 사람의 강아지 번호가 같으면 연결
					if(c.like == d.disLike || c.disLike == d.like)
					{
						adList[i + 1].add(j + 1);
					}
				}
			}
			
			int cnt = 0;
			
			for(int i=1; i<=cat.size(); i++)
			{
				++time;
				if(dfs(i))
					++cnt;
			}
			
			sb.append(V - cnt).append('\n');
		}
		System.out.print(sb);
	}
	static boolean dfs(int now)
	{
		for(int next : adList[now])
		{
			if(visitTime[next] == time)
				continue;
			
			visitTime[next] = time;
			
			if(match[next] == 0 || dfs(match[next]))
			{
				match[next] = now;
				return true;
			}
		}
		return false;
	}
	static void clear()
	{
		cat.clear();
		dog.clear();
		for(int i=0; i<=501; i++)
		{
			match[i] = 0;
			adList[i].clear();
		}
	}
	static void init()
	{
		match = new int[502];
		visitTime = new int[502];
		adList = new ArrayList[502];
		cat = new ArrayList<>();
		dog = new ArrayList<>();
		for(int i=0; i<=501; i++)
			adList[i] = new ArrayList<>();
	}
	static class Node
	{
		int like, disLike;
		Node(int l, int d)
		{
			like = l;
			disLike = d;
		}
	}
}