#17471. 게리맨더링

Problem

• 문제링크

Solution

• city[n][j] = n번째 구역과 인접한구역 j는 1로 표시, 아니면 0으로 표시

1. 한 지역의 구역을 정한다. (중복x, 오름차순으로) - (1,2,3) 과 (2,1,3)은 같은 조합이기에

2. 정한 구역이 이어져 있는지 DFS를 통해 확인한다.

   1. 방문표시

   2. 전체 구역 탐색하여 해당 지역에 속하고 인접할 때, 해당 구역 탐색

      DFS 시작 지점은 해당 지역에서 한 구역으로 지정한다. (그래야 모두 인접해있는지 확인 가능)

      2개의 지역 모두 DFS 탐색 후에 check 표시가 모두 되어있지 않으면 return한다.

      규칙에 맞게 구역이 나누어져 있지 않다는 뜻이기 때문이다.

1 Try

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int N, ans = 1e9;
bool selected[11];
int people[11];
int city[11][11];
bool check[11];
void getDifference() {
	int a_sum = 0, b_sum = 0;
	for (int i = 1; i <= N; ++i) {
		if (selected[i]) a_sum += people[i];
		else b_sum += people[i];
	}
	int res = abs(a_sum - b_sum);
	if (res < ans) ans = res;
}
void DFS(int n, int status) {
	check[n] = true;
	for (int i = 1; i <= N; ++i) {
		if (check[i]) continue;
		if (status == 1) {
			if (selected[i] && city[n][i]) {
				check[i] = true;
				DFS(i, status);
			}
		}
		else {
			if (!selected[i] && city[n][i]) {
				check[i] = true;
				DFS(i, status);
			}
		}
	}
}
void Solve() {
	memset(check, 0, sizeof(check));
	for (int i = 1; i <= N; ++i) {
		if (selected[i]) {
			DFS(i, 1); break;
		}
	}
	for (int i = 1; i <= N; ++i) {
		if (!selected[i]) {
			DFS(i, 0); break;
		}
	}
	for (int i = 1; i <= N; ++i) {
		if (!check[i]) return;
	}
	getDifference();
}
void SelectArea(int n, int cnt) {
	if (cnt >= N) return;
	if (cnt >= 1) {
		Solve();
	}
	for (int i = n; i <= N; ++i) {
		if (selected[i]) continue;
		selected[i] = true;
		SelectArea(i, cnt + 1);
		selected[i] = false;
	}
}
int main() {
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> people[i];
	}
	for (int i = 1; i <= N; ++i) {
		int cnt; cin >> cnt;
		for (int j = 0; j < cnt; ++j) {
			int n; cin >> n;
			city[i][n] = 1;
		}
	}
	SelectArea(1, 0);
	if (ans == 1e9) ans = -1;
	cout << ans << "\n";
	return 0;
}