[BOJ] 17471 : 게리맨더링 - travelbeeee

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

---

[ 알고리즘풀이 ]

1. N이 최대 10이므로 1 ~ N을 A, B 두 그룹으로 나눌 수 있는 모든 경우에 대해서 백트레킹으로 모든 경우의 수를 구하고, 각 경우마다 투표를 진행합니다.

2. 투표를 진행할 때, 현재 A, B로 나누어진 선거구가 투표가 가능한지 체크를 해줍니다.

먼저, A, B 두 그룹 중 하나라도 비어있으면 안 됩니다. 또, A, B 두 그룹이 각각 연결되어있어야 합니다.

따라서 어떤 그룹이 비어있는지 아닌지 체크를 먼저 하고, 그 그룹에 해당되는 지역들을 제외하고 나머지 지역은 visited 에 check를 한 후 BFS 탐색을 진행해 그룹에 속해있는 지역들끼리 서로 연결되어있는지 확인합니다.

3. (2) 에서 투표가 가능하다면, 각 선거구 별로 인구수를 계산해 답을 갱신합니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

int N, M, K, ans = 987654321;
int population[11] = {};
bool map[11][11] = {};
vector<int> A, B;

bool checkPossible(vector<int> K) {
	if (K.empty())
		return false;
	bool visited[11] = {};
	for (int i = 1; i <= N; i++)
		visited[i] = true;
	for (int i = 0; i < K.size(); i++)
		visited[K[i]] = false;
	// BFS탐색
	queue<int> q;
	q.push(K[0]);
	visited[K[0]] = true;
	while (!q.empty()) {
		int s = q.front();
		q.pop();
		for(int i = 1; i <= N; i++)
			if (map[s][i] == 1 && visited[i] == false) {
				visited[i] = true;
				q.push(i);
			}
	}
	for (int i = 1; i <= N; i++)
		if (visited[i] == false)
			return false;
	return true;
}

void playVote() {
	int sumA = 0, sumB = 0;
	if (checkPossible(A) && checkPossible(B)) {
		for (int i = 0; i < A.size(); i++)
			sumA += population[A[i]];
		for (int i = 0; i < B.size(); i++)
			sumB += population[B[i]];
		ans = min(ans, abs(sumA - sumB));
	}
	return;
}
void func(int c) {
	if (c == N) {
		playVote();
		return;
	}
	A.push_back(c + 1);
	func(c + 1);
	A.pop_back();
	B.push_back(c + 1);
	func(c + 1);
	B.pop_back();
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> population[i];
	for (int i = 1; i <= N; i++) {
		cin >> M;
		for (int j = 0; j < M; j++){
			cin >> K;
			map[i][K] = true;
			map[K][i] = true;
		}
	}
	func(0);
	if (ans == 987654321)
		cout << "-1\n";
	else
		cout << ans;
	return 0;
}

---