[BOJ][삼성기출] 17471. 게리맨더링

문제

게리맨더링

문제 접근

완전탐색+BFS 문제이다.

문제 흐름

1. M개의 선거구 고르기
   M(1 ~ N-1) 개의 선거구를 고른다.
   선거구를 두 영역으로 나누는 문제를 한 영역에 포함시킬 선거구를 고르는 문제로 정의하여 해결.

2. 선거구가 잘 나뉘어졌는지 확인
   각 영역이 연결되어 있는지 확인해야 한다. BFS를 사용하여 풀었다.

M의 최댓값은 N-1이기 때문에 무조건 선거구는 두 영역으로 나뉘게 된다. (영역 0과 영역 1)
우선, 영역 1에 포함된 구역 중 하나를 큐에 넣고, 연결된 구역들을 탐색한다. (BFS)
탐색이 끝난 후(is_visit 배열은 방문한 구역에 대해 1의 값을 가짐) 영역 1에 포함된 구역이 모두 방문이 되었는지 확인한다.
이 과정을 영역 0에 대해서도 반복한 뒤, 영역 1과 영역 0이 모두 가능한 방법이라면 두 영역의 인구 수의 차이를 계산하도록 했다.

관건1. 선거구가 잘 나뉘어졌는지 확인

이 문제를 BFS로 풀 때, 큐에 최초로 넣을 노드가 하나여야 한다. (모두 연결되어 있다면 BFS를 통해 어차피 다 방문이 될 것이기 때문, 하나로 시작되지 않는다면 연결되지 않는 상태까지 포함하여 탐색하게 됨.)
연결된 노드 중 같은 영역에 속한 노드만 큐에 넣어야 함을 주의해야 한다.

풀이

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <limits.h>
#include <cmath>
using namespace std;

int N, M, rst, Check;
int map[11];
int info[11];
vector<int> Nodes[11];
bool valid_once;

void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> map[i];
	}
	for (int i = 1; i <= N; i++) {
		int num;
		cin >> num;
		for (int j = 0; j < num; j++) {
			int n;
			cin >> n;
			Nodes[i].push_back(n);
		}
	}
	rst = INT_MAX;
	valid_once = false;
	memset(info, 0, sizeof(info));
}

int is_test_valid() {
	bool is_valid[2];
	for (Check = 1; Check >= 0; Check--) {
		queue<int> Q;
		int is_visit[11];
		memset(is_visit, 0, sizeof(is_visit));
		bool flag = false;

		for (int i = 1; i <= N; i++) {
			if (info[i] == Check) { // 선거구 1에 속한 노드 i에 대하여
				is_visit[i] = 1;
				Q.push(i);
				flag = true;
			}
			if (flag) break; // 모두 연결되어 있는지 확인하는 것이기 때문에, 노드 하나만 넣어서 BFS
		}

		while (!Q.empty()) {
			int i = Q.front(); Q.pop();
			for (int j = 0; j < Nodes[i].size(); j++) { // i와 연결된 노드를 큐에 넣는다.
				if (!is_visit[Nodes[i][j]] && info[Nodes[i][j]] == Check) { // 노드 중 아직 방문되지 않았고, 같은 선거구에 속한 노드일 경우
					is_visit[Nodes[i][j]] = 1;
					Q.push(Nodes[i][j]);
				}
			}
		}

		//연결된 노드 확인이 끝나면, 이 노드가 현재 정한 선거구랑 일치하는지 확인
		flag = true;
		for (int node = 1; node <= N; node++) {
			if (info[node] == Check) {
				if (is_visit[node] != 1) {
					flag = false;
					break;
				}
			}
		}
		is_valid[Check] = flag;
	}

	if (is_valid[0] && is_valid[1]) return true;
	else return false;
}

int calculate_diff() {
	int sum[2] = { 0, 0 };
	for (int state = 0; state <= 1; state++) {
		for (int i = 1; i <= N; i++) {
			if (info[i] == state) sum[state] += map[i];
		}
	}
	return abs(sum[0] - sum[1]);
}

void dfs(int node, int cnt) {
	if (cnt == M) {
		if (is_test_valid()) {
			valid_once = true;
			int diff = calculate_diff();
			rst = min(diff, rst);
		}
		return;
	}
	for (int i = node + 1; i <= N; i++) {
		info[i] = 1;
		dfs(i, cnt + 1);
		info[i] = 0;
	}
}

void solve() {
	for (int m = 1; m <= N - 1; m++) {
		M = m;
		for (int i = 1; i <= N; i++) {
			info[i] = 1;
			dfs(i, 1);
			info[i] = 0;
		}
	}
	if (!valid_once) rst = -1;
}

int main() {
	input();
	solve();
	cout << rst << endl;
}