백준11014 컨닝 2

작성일 | In

문제 링크

  • http://icpc.me/11014

문제 출처

  • 2008 Google Code Jam Round3 C2번

사용 알고리즘

  • 이분 매칭
  • 최대 독립 집합

시간복잡도

  • O(N2M2)

풀이

격자는 이분 그래프입니다.

각 학생은 자신의 {왼쪽, 오른쪽, 왼쪽 앞, 오른쪽 앞} 자리의 답을 배낄 수 있습니다.
배낄 수 있는 자리는 모두 왼쪽 혹은 오른쪽 줄에 위치합니다. 자신이 속한 줄에 존재하는 자리의 답을 배낄 수 없습니다.

배낄 수 있는 자리들을 간선으로 잇고 짝수번째 줄과 홀수번째 줄을 분리해주면, 이분 그래프가 나오게 됩니다.

이분 매칭을 잘 해줍시다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;

int arr[88][88];
vector<int> g[8080];
int par[8080];
int chk[8080];
int n, m;

const int di[] = {1, 1, 0, 0, -1, -1};
const int dj[] = {-1, 1, -1, 1, -1, 1};

int f(int i, int j){
	return i * 80 + j;
}

void init(){
	memset(arr, 0, sizeof arr);
	for(int i=0; i<8080; i++) g[i].clear();
	memset(par, -1, sizeof par);
}

bool dfs(int v){
	for(auto i : g[v]){
		if(chk[i]) continue;
		chk[i] = 1;
		if(par[i] == -1 || dfs(par[i])){
			par[i] = v; return 1;
		}
	}
	return 0;
}

void solve(){
	init();
	cin >> n >> m;
	int sum = 0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			char t; cin >> t;
			arr[i][j] = t == 'x';
			sum += t == '.';
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			for(int k=0; k<6; k++){
				if(arr[i][j]) continue;
				int ii = i + di[k];
				int jj = j + dj[k];
				if(ii < 1 || ii > n || jj < 1 || jj > m) continue;
				if(arr[ii][jj]) continue;
				g[f(i, j)].push_back(f(ii, jj));
			}
		}
	}

	int ans = 0;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j+=2){
			if(arr[i][j]) continue;
			memset(chk, 0, sizeof chk);
			chk[f(i, j)] = 1;
			ans +=  dfs(f(i, j));
		}
	}
	cout << sum - ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--) solve();
}