[백준] 17471번 게리맨더링

17471번: 게리맨더링

두 선거구로 나눌 때 각 선거구 안에 있는 영역들은 모두 연결되어 있는 상태여야 한다.

그러므로 두  선거구로 나눌 수 없는 경우는

연결되어 있는 그룹이 세 개 이상일 때이므로

이 경우를 가려주기 위해

먼저 BFS로 연결된 그룹이 몇 개인지 세어준다.

3개 이상일 경우 -> -1 출력

2개일 경우 -> 두 그룹이 각각 선거구이므로 이때 인구의 차 출력

1개일 경우 -> 모두 연결된 상태이므로 다음 단계 넘어감

 

두 선거구로 나누는 방법은

N개 중에서 K개를 순서 상관없이 뽑는 조합으로 구할 수 있다.

여기서 K의 범위는 1 <= K <= N/2 이다.

그 이유는

N은 3, K는 1이라고 가정할 때

선거구1   선거구2

1       2, 3

2       1, 3

3       1, 2

를 뽑을 수 있고

 

N은 3, K는 2라고 가정할 때

선거구1  선거구2

1, 2        3

1, 3        2

2, 3        1

를 뽑을 수 있다.

 

이때 K가 2일 때 선거구1은

K가 1일 때 선거구2와 같고

K가 2일 때 선거구2는

K가 1일 때 선거구1과 같다.

이렇게 중복되는 연산을 하지 않기 위해

K의 범위를 1부터 N/2까지로 지정한 것이다.

그러면 N이 3일 땐 K는1일 때까지만 연산을 하면 된다.

 

이렇게 나눈 두 선거구를

각 선거구의 영역들이 전부 연결되어 있는지 BFS로 판단해주고

두 선거구 모두 연결되어 있는 상태라면 그때의 인구의 차를 계산한다.

 

비교가 모두 끝나면 최솟값을 출력하면 된다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
int N, res, M, tmp, tmp2, Min = 10000;
int population[11], group[11];
bool visited[11] = { false };
vector <int> v[11], connected;
queue <int> q;
void Bfs() { //모두 연결되어 있는지 확인
	while (!q.empty()) {
		int idx = q.front();
		for (int i = 0; i < v[idx].size(); i++) {
			if (!visited[v[idx][i]]) {
				q.push(v[idx][i]);
				visited[v[idx][i]] = true;
			}
		}
		tmp2 += population[idx];
		q.pop();
	}
}
void Bfs2(int num) { //각 그룹이 모두 연결되어 있는지 확인
	while (!q.empty()) {
		int idx = q.front();
		for (int i = 0; i < v[idx].size(); i++) {
			if (group[v[idx][i]] == num) {
				q.push(v[idx][i]);
				group[v[idx][i]] = num + 2;
			}
		}
		q.pop();
	}
}
void Combination(int idx, int cnt, int goal) {
	if (cnt == goal) {
		for (int n = 1; n >= 0; n--) {
			for (int i = 1; i <= N; i++) {
				if (group[i] == n) {
					q.push(i), group[i] = n + 2;
					Bfs2(n); //각 그룹이 연결되어 있는지 확인
					int count = 0;
					for (int j = 1; j <= N; j++) if (group[j] == n) count++;
					for (int j = 1; j <= N; j++) if (group[j] == n + 2) group[j] = n; //초기화
					if (count != 0) return; //다 연결이 안 된 경우
					else break;
				}
			}
		}
		Min = min(Min, abs(tmp - abs(res - tmp))); //두 그룹 다 연결된 영역으로 구성되어 있으면 인구 차 구함
		return;
	}
	for (int i = idx; i <= N; i++) {
		tmp += population[i], group[i] = 1;
		Combination(i + 1, cnt + 1, goal);
		tmp -= population[i], group[i] = 0;
	}
}
int main() {
	cin >> N;
	for (int n = 1; n <= N; n++) {
		cin >> population[n];
		res += population[n];
	}
	for (int i = 1; i <= N; i++) {
		cin >> M;
		for (int j = 0; j < M; j++) {
			cin >> tmp;
			v[i].push_back(tmp);
		}
	}
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			tmp2 = 0, q.push(i), visited[i] = true;
			Bfs();
			connected.push_back(tmp2);
		}
	}
	if (connected.size() > 2) cout << -1; //두 선거구로 나눌 수 없는 경우
	else if (connected.size() == 2) cout << abs(connected[0] - connected[1]); //두 선거구가 연결이 되어있지 않은 경우
	else { //구역이 모두 연결되어 있는 경우
		for (int i = 1; i <= N / 2; i++) {
			tmp = 0;
			Combination(1, 0, i);
		}
		cout << Min;
	}	
	return 0;
}