[BOJ]백준 17471번: 게리 맨더링

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

17471번: 게리맨더링

완전탐색으로 그래프를 두 구로 나누어 각각 연결요소의 개수를 구하고, 2개일 경우에만 차이의 최솟값을 구하는 문제

이런식으로

크게 세 부분으로 나뉜다.

1. N개의 구를 두 진영으로 나누는 경우의 수 구하기

2. 각각의 요소들을 BFS로 연결요소가 두 개인지 구하기

3. 두 연결요소의 차의 최솟값 구하기

 

일단

1. 백트래킹을 이용해서 depth가 N일 때 까지 콜스택을 쌓고

2. 1번 요소에서 BFS를 돌려서 전부 visit됐다면? / 그 다음 요소에서 BFS했는데 visit되지 않은 요소가 있다면? -> Fail

3. ans값 갱신

많이 어렵지는 않은 문제였다

#include <cstdio>
#include <queue>
using namespace std;
int n, p[11], ans=10000000;
bool graph[11][11], gu[11], visit[11];
queue<int> q;
int bfs(int num) {
	int k = 1;
	visit[num] = true;
	q.push(num);
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (int t = 1; t <= n; t++) {
			if (graph[cur][t] && !visit[t] && gu[cur] == gu[t]) {
				visit[t] = true;
				q.push(t); k++;
			}
		}
	}
	return k;
}
void func(int dep) {
	if (dep > n) {
		int red = 0, blue = 0, sub,j;
		for (int i = 1; i <= n; i++)visit[i] = false;

		red = bfs(1);
		if (red == n)return;
		
		for (j = 2; j <= n; j++)
			if (!visit[j]) {
				blue=bfs(j); break;
			}
		if (red + blue != n)return;
		red = blue = 0;

		for (int i = 1; i <= n; i++)
			if (gu[i])red += p[i];
			else blue += p[i];
		sub = red > blue ? red - blue : blue - red;
		ans = sub < ans ? sub : ans;
		return;
	}

	gu[dep] = 0;
	func(dep + 1);
	gu[dep] = 1;
	func(dep + 1);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &p[i]);
	for (int i = 1,t,j; i <= n; i++) {
		scanf("%d", &t);
		while (t--) {
			scanf("%d", &j);
			graph[i][j] = true;
			graph[j][i] = true;
		}
	}
	func(1);
	printf("%d", ans==10000000?-1:ans);
	return 0;
}