[백준] 17471 게리맨더링

[백준] 17471 게리맨더링

• https://www.acmicpc.net/problem/17471

#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include <math.h>
#include <algorithm>
using namespace std;

int N;
vector<vector<int>> adj(11, vector<int>(11, 0));


//가능한 모든 선거구역 저장
vector<string> bitmasks;
void buildBitmasks(string bitmask) {
	if (bitmask.length() == N) {
		bitmasks.push_back(bitmask);
		return;
	}

	buildBitmasks(bitmask + "0");
	buildBitmasks(bitmask + "1");
}

//start에서 시작해서 그래프 bfs 순회
//bitmask에 표시된 노드 모두 방문하였는지 bool 반환
bool bfs(int start, string bitmask) {
	vector<int> visited(N, 0);

	queue<int> q;
	q.push(start);

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		if (visited[cur]) continue;
		visited[cur] = 1;

		for (int next = 0; next < N; ++next) {
			if (!adj[cur][next]) continue;
			//다른 선거구에 포함되어있는 노드로 갈 수 없음
			if (bitmask[next] == '0') continue;
			if (visited[next]) continue;
			q.push(next);
		}
	}

	//bitmask에 표시된 노드 모두 방문했는지 확인
	for (int i = 0; i < N; ++i) {
		if (visited[i]) bitmask[i] = '0';
	}
	if (stoi(bitmask) == 0) return true;
	return false;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;

	//인구수 입력받기
	vector<int> people(11, 0);
	for (int i = 0; i < N; ++i) {
		int pp;
		cin >> pp;
		people[i] = pp;
	}

	//서로 인접한 노드 입력받기
	for (int a = 0; a < N; ++a) {
		int M;
		cin >> M;
		for (int j = 0; j < M; ++j) {
			int b;
			cin >> b;
			b--;

			adj[a][b] = 1;
			adj[b][a] = 1;
		}
	}

	//가능한 모든 선거구역 경우의 수 구하기
	buildBitmasks("");

	int minDiff = 987654321;
	for (int i = 0; i < bitmasks.size(); ++i) {
		string area1 = bitmasks[i];
		string area2 = "";
		for (int j = 0; j < N; ++j) {
			if (area1[j] == '0') area2 += "1";
			else area2 += "0";
		}

		//아무 노드도 포함되지 않은 경우
		if (stoi(area1) == 0) continue;
		if (stoi(area2) == 0) continue;

		//bfs시작을 위한 선거구 1, 2에 포함된 노드 찾기
		int start1 = -1;
		int start2 = -1;
		for (int j = 0; j < N; ++j) {
			if (area1[j] == '1') start1 = j;
			else start2 = j;

			if ((start1 != -1) && (start2 != -1)) break;
		}

		//선거구 1 서로 연결되어있는지 확인
		if (!bfs(start1, area1)) continue;

		//선거구 2 서로 연결되어있는지 확인
		if (!bfs(start2, area2)) continue;

		//인구수 차이 구하기
		int sum1 = 0;
		int sum2 = 0;
		for (int j = 0; j < N; ++j) {
			if (area1[j] == '1') sum1 += people[j];
			else sum2 += people[j];
		}

		minDiff = min(minDiff, abs(sum1 - sum2));
	}


	if (minDiff == 987654321) cout << -1;
	else cout << minDiff;
	return 0;
}