[BOJ] 백준 11014, 1014. 컨닝 2 (Platinum II)

굉장히 유명한 문제.

문제는 아래와 같다.

https://www.acmicpc.net/problem/11014

11014번: 컨닝 2

1014번 컨닝은 N, M 제한이 80이 아니라 10이라는 점 외엔 11014번과 동일하다.

---

의식의 흐름 및 해설

사실 이 문제는 너무나도 유명한 문제여서 최대유량, bitmask+dp 로 풀어야한다는 사실 자체는 알고 있었던 문제이다.

그러나 왜 최대유량으로 풀리는지 모르는 상태였기 때문였었고,

마침 우연히 최근에 flow 관련 그래프 이론을 공부중이기 때문에 한번 시도해보았다.

 

조건을 만족하면서 학생을 최대한 많이 앉혀야 한다.

같은 열끼리는 학생을 앉혀도 상관이 없으며, 컨닝하는 학생들끼리 영향을 미치는 여부를 그래프로 그려보면, 이분그래프 형태가 나옴을 알 수 있다.

사실 문제 알고리즘 분류 스포로 떠올린 것도 없지않아 있는 듯하다.

 

이분그래프가 그려질 수 있고, 컨닝할 수 있는 매칭을 최대한으로 구해보는 그림이 나오므로 최대유량을 떠올릴 수 있다. 

컨닝할 수 있는 매칭을 최대한으로 한다는 것은, Maximum Independent Set을 최대한으로 구해보겠다는 뜻이며, 이는 Minimum Vertex Cover의 여집합이다.

따라서 Konig의 이론에 따라 Maximum Bipartite Matching의 값을 N*M에서 빼주면 된다.

Bipartite Matching으론, 왼/오/위왼/위오/아래왼/아래오 이렇게 여섯방향을 단방향 매칭해주면 된다.

또한, x자리는 앉을 수 없으므로 아예 고려대상에서 제외한다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
const int MAX = 83;
const int INF = 0x3f3f3f3f;
const int LNF = 1e18;
const int MOD = 1e9 + 7;
int N, M, d[MAX*MAX];
char a[MAX][MAX];
vector<int> v[MAX*MAX];
bool used[MAX * MAX], able[MAX * MAX];
bool dfs(int cur) {
	for (auto i : v[cur]) {
		if (used[i])
			continue;
		used[i] = true;
		if (d[i] == -1 || dfs(d[i])) {
			d[i] = cur;
			return true;
		}
	}
	return false;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin >> t;
	while (t--) {
		for (int i = 0; i < MAX * MAX; i++) {
			v[i].clear();
			able[i] = false;
			d[i] = -1;
		}
		cin >> N >> M;
		int ans = N * M, res = 0;
		for (int i = 0; i < N; i++) {
			string s;
			cin >> s;
			for (int j = 0; j < M; j++) {
				a[i][j] = s[j];
				if (a[i][j] == 'x')
					ans--;
				else
					able[i*M+j] = true;
			}
		}
		for (int j = 0; j < M; j+=2) {
			for (int i = 0; i < N; i++) {
				int cur = i * M + j;
				if (able[cur]) {
					int left = cur - 1;
					int right = cur + 1;
					int downLeft = left + M;
					int downRight = right + M;
					int upLeft = left - M;
					int upRight = right - M;
					if (j && able[left])
						v[cur].push_back(left);
					if (j != M - 1 && able[right])
						v[cur].push_back(right);
					if (i != N - 1 && j && able[downLeft])
						v[cur].push_back(downLeft);
					if (i != N - 1 && j != M - 1 && able[downRight])
						v[cur].push_back(downRight);
					if (i && j && able[upLeft])
						v[cur].push_back(upLeft);
					if (i && j != M - 1 && able[upRight])
						v[cur].push_back(upRight);
				}
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				int cur = i * M + j;
				fill(used, used + MAX * MAX, false);
				if (dfs(cur))
					res++;
			}
		}
		cout << ans - res << "\n";
	}
}

---

심오한 그래프 세계...

조합론과 그래프 이론을 잘 공부해야 하는 이유인 듯하다.

나중에 수교과 수업 들을 수 있다면 들어볼까 생각도 드는 하루다.