[BOJ] #17471 _ 게리맨더링

[게리맨더링] https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

두 구역으로 나눌 수 있는 모든 경우의 수를 고려하여 인구 차이의 최솟값을 구하는 문제이다.

next_permutation을 통해 구현하였다.

알고리즘의 흐름은 다음과 같다.

 

1. 경우의 수 만들기 (1:N, 2:N-2 ...)

2. 각 구역의 연결 유무 확인

3. 두 구역 모두 연결되어 있다면, 인구 수 차이 구하기

 

checkConnection()의 매개변수인 type은 1구역 2구역을 나타내는 변수이고,

possible배열은 연결 유무의 값을 담고있는 배열이다.

 

[ 소스 코드 ]

#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 11

using namespace std;
int N, people[MAX], min_val = 999999999;
vector<int> connect[MAX], v;

void solve();
int checkConnection(int type);
int main() {
	int tmp, tmp_town;

	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d", &people[i]);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &tmp);
		for (int j = 0; j < tmp; j++) {
			scanf("%d", &tmp_town);
			connect[i].push_back(tmp_town);
		}
	}
	solve();

	if (min_val == 999999999) min_val = -1;
	printf("%d\n", min_val);

	return 0;
}

void solve() {
	for (int i = 0; i < N/2; i++) {
		for (int j = 0; j < N; j++) {
			if (j <= i) v.push_back(0);
			else v.push_back(1);
		}

		do {
			int num1 = 0, num2 = 0;
			if (!checkConnection(0)) continue;
			if (!checkConnection(1)) continue;
			for (int j = 1; j <= N; j++) {
				if (v[j-1]) num1 += people[j];
				else num2 += people[j];
			}
			min_val = min(min_val, abs(num1 - num2));
		} while (next_permutation(v.begin(), v.end()));

		v.clear();
	}
}

int checkConnection(int type) {
	queue<int> q, town;
	int chk[MAX], possible[MAX];

	for (int i = 1; i <= N; i++) { // 갈 수 없는 곳 초기화
		if (type == 0) {
			chk[i] = v[i-1];
		}
		else {
			if (v[i-1]) chk[i] = 0;
			else chk[i] = 1;
		}
		possible[i] = 0;
		if (v[i-1] == type) town.push(i);
	}
    
//연결 유무 확인
	for (int i = 0; i < connect[town.front()].size(); i++) q.push(connect[town.front()][i]);

	possible[town.front()] = 1;
	chk[town.front()] = 1;
	int tmp;
	while (!q.empty()) {
		tmp = q.front();
		q.pop();
		if (chk[tmp]) continue;
		possible[tmp] = 1;
		chk[tmp] = 1;
		for (int i = 0; i < connect[tmp].size(); i++) q.push(connect[tmp][i]);
	}

	while (!town.empty()) {
		if (!possible[town.front()]) return 0;
		town.pop();
	}
	
	return 1;
}