취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11495번 문제인 격자 0 만들기이다.
문제는 아래 링크를 확인하자.

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

주어지는 격자의 각 칸을 노드, 인접한(한 변을 공유하는) 칸끼리를 연결관계로 갖는 그래프는 이분그래프(bipartite graph)가 된다는 점을 이용하자. 이 때, 이분그래프의 각 노드는 체스판의 흰 칸과 검은 칸의 구분과 같은 식으로 이루어진다.

이제, source에서 흰 칸으로 각 칸에 적힌 수만큼 , 검은 칸에서 sink로 각 칸에 적힌 수만큼, 그 외의 격자에서 인접한 칸 사이의 이동에 무한대만큼의 용량을 주는 방향그래프를 만들어 source에서 sink로의 최대 유량을 구하면 이 값은 "두 칸에서 1을 각각 지울 수 있는 최대 횟수"를 의미하게 된다.

위에서 구한 값과 "전체 1의 개수", 즉 모든 격자칸의 수의 합을 이용해 답을 계산해내면 문제가 해결된다.

아래는 제출한 소스코드이다.

#define NODE 2502
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int source, sink;
int edge[NODE][NODE];
vector<int> G[NODE];
int level[NODE];

bool dinic_bfs() { // 현 단계의 level graph 생성; 리턴값: 성공여부
	memset(level, 0, sizeof(level));
	level[source] = 1;
	queue<int> que;
	que.push(source);
	while (!que.empty()) {
		int& cur = que.front();
		for (auto& node : G[cur]) {
			if (edge[cur][node] && level[node] == 0) {
				level[node] = level[cur] + 1;
				que.push(node);
			}
		}
		que.pop();
	}

	return level[sink];
}

int turn[NODE];

int dinic_dfs(int cur, int flow) { // flow값 오버플로우 주의
	if (cur == sink) return flow;
	int cursize = G[cur].size();
	for (int& i = turn[cur]; i < cursize; i++) {
		int& node = G[cur][i];
		if (edge[cur][node] && level[node] == level[cur] + 1) {
			int tmp = dinic_dfs(node, min(edge[cur][node], flow));
			if (tmp) {
				edge[cur][node] -= tmp;
				edge[node][cur] += tmp;
				return tmp;
			}
		}
	}

	return 0;
}

int dinic() { // 실제 maximum flow 계산, 오버플로우 유의
	int ret = 0;
	while (dinic_bfs()) {
		memset(turn, 0, sizeof(turn));
		int f;
		while (f = dinic_dfs(source, 1000000007)) ret += f;
	}

	return ret;
}

int R, C;
int arr[50][50];
int idx[50][50];
void solve() {
	cin >> R >> C;
	source = 0, sink = R * C + 1;
	for (int i = source; i <= sink; i++) G[i].clear();
	memset(edge, 0, sizeof(edge));

	int total = 0;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> arr[r][c];
			idx[r][c] = r * C + c + 1;
			total += arr[r][c];
		}
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			int i = idx[r][c];
			if ((r + c) & 1) G[i].emplace_back(sink), G[sink].emplace_back(i), edge[i][sink] = arr[r][c];
			else {
				G[source].emplace_back(i), G[i].emplace_back(source), edge[source][i] = arr[r][c];
				if (c > 0) G[i].emplace_back(i - 1), G[i - 1].emplace_back(i), edge[i][i - 1] = 10000;
				if (c < C - 1) G[i].emplace_back(i + 1), G[i + 1].emplace_back(i), edge[i][i + 1] = 10000;
				if (r > 0) G[i].emplace_back(i - C), G[i - C].emplace_back(i), edge[i][i - C] = 10000;
				if (r < R - 1) G[i].emplace_back(i + C), G[i + C].emplace_back(i), edge[i][i + C] = 10000;
			}
		}
	}

	cout << total - dinic() << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		solve();
	}
}