[백준][비트마스킹] 17471 게리맨더링 c++구현

목차

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

문제

 

코드 구현 방향

비트 마스킹을 통해 나누어지는 경우를 모두 구하고 조건을 만족하는지 체크하여 최솟값을 갱신하였다.

(영역을 색칠한는 방식으로 하면 코드를 더 간결하게 작성할 수 있었을 것 같다...)

 

코드 구현

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<math.h>

using namespace std;

int N;
vector<int> person;
vector<int> adj[11];
int visit[20] = { 0 };
int Gap = 999;
vector<int> a;
vector<int>b;

//안에 있는지 체크 함수
int incheck(int n, vector<int>& c) {
	for (int i = 0; i < c.size(); i++) {
		if (c[i] == n)
			return 1;
	}
	return 0;
}

//모두 다 탐색이 됬는지 확인하는 함수
int count() {
	int cnt = 0;
	for (int i = 0; i < 20; i++) {
		if (visit[i] == 1)
			cnt++;
	}
	if (cnt == N)
		return 1;
	else
		return 0;
}

//bfs로 모두 탐색
void bfs(int start, int start2) {
	fill(visit, visit + 20, 0);
	queue<int> q;
	q.push(start);
	visit[start] = 1;
	
	while (!q.empty()) {
		int n = q.front();
		q.pop();
		for (int i = 0; i < adj[n].size(); i++) {
			if (!visit[adj[n][i]] && incheck(adj[n][i], a)) {
				q.push(adj[n][i]);
				visit[adj[n][i]] = 1;
			}
		}
	}
	queue<int> q2;
	q2.push(start2);
	visit[start2] = 1;
	while (!q2.empty()) {
		int n = q2.front();
		q2.pop();
		for (int i = 0; i < adj[n].size(); i++) {
			if (!visit[adj[n][i]] && incheck(adj[n][i], b)) {
				q2.push(adj[n][i]);
				visit[adj[n][i]] = 1;
			}
		}
	}
}


void check() {
	if (a.size() == 0 || b.size() == 0)
		return;
	bfs(a[0], b[0]);
    
	//조건 일치시 최솟값 갱신
	if (count()) {
		int A = 0;
		int B = 0;
		for (auto k : a) {
			A += person[k-1];
		}
		for (auto k : b) {
			B += person[k-1];
		}
		int g = abs(B - A);
		Gap = min(Gap, g);
	}
	
}

// 비트마스킹으로 모든 경우 탐색
void search() {
	for (int i = 0; i < (1 << N); i++) {
		a.clear();
		b.clear();
		for (int j = 0; j < N; j++) {
			if (i & (1 << j))
				a.push_back(j+1);
			else
				b.push_back(j+1);
		}

		check();
	}
}


int main() {
	int num, s;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num;
		person.push_back(num);
	}
	for (int i = 1; i <= N; i++) {
		cin >> num;
		for (int j = 0; j < num; j++) {
			cin >> s;
			adj[i].push_back(s);
			adj[s].push_back(i);
		}
	}
	search();
	if (Gap == 999)
		cout << -1;
	else
	    cout << Gap;
	
}