[백준 2188번] 축사 배정 - 이분 매칭 고찰하기

www.acmicpc.net/problem/2188

2188번: 축사 배정

이분 매칭 알고리즘을 구현하기만 하면 통과하는 문제라 문제 풀이보단

이분 매칭에 대한 고찰 몇 가지를 남기려 합니다.

 

아래는 정답 코드입니다.

 

...
/*
백준 2188번 - 축사 배정
https://www.acmicpc.net/problem/2188
*/
public class Main {
	static int[][] edges; // 간선 [cow][barn]
	static int[] aMatch, bMatch;
	static boolean[] visited;
	static int N,M;
	public static void main(String[] args) throws IOException {
//		BufferedReader br = new BufferedReader(new FileReader("testcase.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
		edges = new int[N][M];
		for (int cowNum = 0; cowNum < N; cowNum++) {
			st = new StringTokenizer(br.readLine());
			int barnSize = Integer.parseInt(st.nextToken());
			for (int i = 0; i < barnSize; i++) {
				int barnNum = Integer.parseInt(st.nextToken())-1;
				edges[cowNum][barnNum] = 1;
			}
		}
		System.out.println(bipartiteMatching());
	}
	// 집합 A의 정점 a에서 B의 매칭되지 않은 정점으로 가는 경로를 찾는다
	public static boolean dfs(int a) {
		if(visited[a]) return false; // 재방문 크트. 매칭 수정시 이 한 줄의 코드가 어떻게 작용하는지 유의할 것.
		visited[a] = true;
		for(int b = 0; b < M; ++b) {
			if(edges[a][b] == 1) {
				//b가 아직 매칭되지 않았다면
				if(bMatch[b] == -1) {
					aMatch[a] = b;
					bMatch[b] = a;
					return true;
				}
				//b가 이미 매칭되어있다면 bMatch[b]에서부터 시작해 경로를 찾는다. 찾았을 경우 재귀 호출한 부분에서 경로를 수정한다.
				if(dfs(bMatch[b])) {
					//dfs 호출(재귀호출)에서 경로를 수정했으니 b에 연결된 정점이 없으므로 연결해준다.
					aMatch[a] = b;
					bMatch[b] = a;
					return true;
				}
			}
		}
		return false;
	}

	public static int bipartiteMatching() {
		aMatch = new int[N]; Arrays.fill(aMatch, -1);
		bMatch = new int[M]; Arrays.fill(bMatch, -1);

		int size = 0;
		for (int start = 0; start < N; start++) {
			visited = new boolean[N];

			// 증가 경로, 즉 매칭을 찾은 경우 1의 유량 증가시킨다. 증가 경로를 찾을때 마다 +1 ?  정당성 증명 필요하다.
			if(dfs(start)) ++size;
		}
		return size;
	}
}

 

 

 

구현은 dfs 방식으로 구현했고 음의 간선 같은 것들이 코드 상에는 나타나지 않지만, 에드몬드 카프 알고리즘과 원리는 동일합니다.

 

처음에 에드몬드 카프 알고리즘과 동일한 원리나는 것을 몰라서 아래의 코드가 왜 정답을 내는지 이해를 못했습니다.

		int size = 0;
		for (int start = 0; start < N; start++) {
			visited = new boolean[N];

			// 증가 경로, 즉 매칭을 찾은 경우 1의 유량 증가시킨다. 증가 경로를 찾을때 마다 +1 ?  정당성 증명 필요하다.
			if(dfs(start)) ++size;
		}
		return size;

 

 

위 코드처럼 순차적으로 dfs하면 반드시 최대 유량(매칭)이 나타난다는 걸 어떻게 증명할 수 있을까? 

 

위 물음에 대해 에드몬드 카프 알고리즘에서는 음의 유량 개념을 이용해 해결합니다. 그런데 위 코드에서 음의 유량같은 개념이 안보이더군요. 그러면 간선의 탐색 순서에 따라 최대 유량이 변하는 케이스가 존재해야 됩니다. 하지만 위 코드에서는 그냥 단순히 순서대로 증가경로를 찾아 유량을 더해주고 있습니다. 제가 모르는 뭔가가 있는것 같네요.

 

 

결론만 말하자면 아래의 코드가 음의 유량 역할을 대신하고 있습니다.

//b가 이미 매칭되어있다면 bMatch[b]에서부터 시작해 경로를 찾는다. 찾았을 경우 재귀 호출한 부분에서 경로를 수정한다.
if(dfs(bMatch[b])) {
	//dfs 호출(재귀호출)에서 경로를 수정했으니 b에 연결된 정점이 없으므로 연결해준다.
	aMatch[a] = b;
	bMatch[b] = a;
	return true;
}

 

만약 이 문제를 에드몬드 카프 알고리즘으로 풀었다면 b가 매칭된 경우, 음의 유량을 이용해 b와 매칭된 a로 거슬러 올라가 경로를 찾기 시작합니다. 위 방식은 음의 유량을 더하는 대신 재귀를 이용해 그 문제를 해결합니다.