[BOJ 1127 // C++] 떡국

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

 

이번에 볼 문제는 백준 1127번 문제인 떡국이다.
문제는 아래 링크를 확인하자.

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

1127번: 떡국

먼저, 각 경비회사의 경비의 고용은 독립적인 사건이라는 점을 눈치채자. 즉 각 경비회사마다 "충돌"을 최소화해 그 값들을 더하는 것으로 문제를 해결할 수 있다는 점을 관찰하자.

 

경비회사 하나만을 두고 볼 때, 각 도시는 다음 세 가지 상태 중 하나에 속한다:

(1) 경비회사가 들어와있고 경비가 이미 고용되어있다.

(2) 경비회사가 들어와있지만 경비가 고용되어있지는 않다.

(3) 경비회사가 들어와있지 않다.

 

이 때 "충돌"의 수의 최솟값은 도시들의 협력관계 그래프에서 (1) 도시들을 source, (3) 도시들을 sink로 갖는 유량 그래프의 min cut과 같다는 점을 발견하자. max-flow min-cut정리에 의해 최대 유량을 구하는 것으로 min cut은 계산할 수 있다.

 

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

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

int ans = 0;
int N, K;
string s[50];
vector<int> guards_of_company[50];
vector<int> cities_of_company[50];
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 arr[52];
void solve(int k) {
	for (auto& v : G) v.clear();
	memset(arr, 0, sizeof(arr));
	memset(edge, 0, sizeof(edge));
	source = N, sink = N + 1;
	for (auto node : guards_of_company[k]) arr[node]++;
	for (auto node : cities_of_company[k]) arr[node]++;
	for (int r = 0; r < N; r++) {
		for (int c = r+1; c < N; c++) {
			if (s[r][c] == '1') {
				if (arr[r] == 0) {
					if (arr[c] == 0) continue;
					else if (arr[c] == 1) {
						edge[c][sink]++;
						G[c].emplace_back(sink);
						G[sink].emplace_back(c);
					}
					else {
						edge[source][sink]++;
						G[source].emplace_back(sink);
						G[sink].emplace_back(source);
					}
				}
				else if (arr[r] == 1) {
					if (arr[c] == 0) {
						edge[r][sink]++;
						G[r].emplace_back(sink);
						G[sink].emplace_back(r);
					}
					else if (arr[c] == 1) {
						edge[r][c]++;
						edge[c][r]++;
						G[r].emplace_back(c);
						G[c].emplace_back(r);
					}
					else {
						edge[source][r]++;
						G[r].emplace_back(source);
						G[source].emplace_back(r);
					}
				}
				else {
					if (arr[c] == 0) {
						edge[source][sink]++;
						G[source].emplace_back(sink);
						G[sink].emplace_back(source);
					}
					else if (arr[c] == 1) {
						edge[source][c]++;
						G[source].emplace_back(c);
						G[c].emplace_back(source);
					}
					else continue;
				}
			}
		}
	}
	ans += dinic();
}

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

	cin >> N;
	for (int r = 0; r < N; r++) cin >> s[r];

	cin >> K;
	for (int n = 0; n < N; n++) {
		int cnt; cin >> cnt;
		while (cnt--) {
			int x; cin >> x;
			guards_of_company[x].emplace_back(n);
		}
	}

	for (int n = 0; n < N; n++) {
		int cnt; cin >> cnt;
		while (cnt--) {
			int x; cin >> x;
			cities_of_company[x].emplace_back(n);
		}
	}

	for (int k = 0; k < K; k++) solve(k);

	cout << ans;
}