백준 / 17471 게리맨더링 C++

www.acmicpc.net/problem/17471

17471번: 게리맨더링

선거 구역을 최대한 공평하게 나누는 게리맨더링 문제입니다.

주어진 그래프에서 선거 구역을 2군데로 나누는데 나누어진 구역들은 모두 1개 이상이어야하고, 모두 이어져 있어야합니다.

 

풀이

1. 가능한 모든 조합을 구한다. 단, 1개 이상 원소 포함

({1,2,3},{4,5,6} 계산 후 {4,5,6},{1,2,3} 계산하는 것과 같이 중복 내용이 포함되지만, worst case가 n=10으로 작은 경우이기에 중복 제거 안해도 될 거 같아 그냥 돌렸습니다.)

2. 각 조합 별로 모두 이어져 있는지 확인합니다.

(두 선거 구역 모두 이어져 있어야 하므로 이를 만족하는 경우만 3번을 합니다.)

3. 가능한 선거 구역이면 사람들을 계산한다.

 

next_permutaion 메서드를 이용해 가능한 모든 조합을 구하였고, bfs를 이용해 해당 선거 구역이 어어져 있는지 확인하였습니다. 

(처음에 bfs 돌릴 때, if(check[구역]==false) 를 체크를 안 해서 큐에 중복 노드가 쌓여서 틀렸었다. 실수하지 말기!)

 

코드는 다음과 같습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

int n;
vector<int>population;
vector<int>graph[11];
vector<vector<int>>comb[6]; // 10/2=5
bool check[11];
int result = 987654321;

void make_graph()
{
	cin >> n;
	population.push_back(0);
	for (int i = 1; i <= n; i++) {
		int num;
		cin >> num;
		population.push_back(num);
	}

	for (int i = 1; i <= n; i++) {
		int location;
		cin >> location;
		for (int j = 1; j <= location; j++) {
			int num;
			cin >> num;
			graph[i].push_back(num);
		}
	}

	memset(check, false, sizeof(check));
}

// nCr의 케이스 모두 구하기
void make_combinations(int r)
{
	vector<int>v;
	for (int i = 1; i <= n; i++)
		v.push_back(i);

	vector<int>ind;
	for (int i = 0; i < r; i++)
		ind.push_back(1);
	for (int i = 0; i < n - r; i++)
		ind.push_back(0);
	sort(ind.begin(), ind.end());

	do {
		vector<int>tmp;
		for (int i = 0; i < ind.size(); i++) {
			if (ind[i] == 1)
				tmp.push_back(v[i]);
		}
		comb[r].push_back(tmp);
		tmp.clear();
	} while (next_permutation(ind.begin(), ind.end()));
}

// v에 있는 애들이 다 연결되었는지 확인
bool possible(vector<int>v)
{
	memset(check, false, sizeof(check));
	queue<int>q;
	q.push(v[0]);
	int cnt = 0;

	while (!q.empty())
	{
		int now = q.front();
		check[now] = true;
		cnt++;
		q.pop();

		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i];
			vector<int>::iterator iter;

			iter = find(v.begin(), v.end(), next);
			if (iter != v.end()) {
				if (check[next] == false) {
					q.push(next);
					check[next] = true;
				}
			}
		}
	}

	if (cnt == v.size())
		return true;
	else
		return false;
}

// v 원소 말고 나머지 애들 구하기
vector<int> others(vector<int>v)
{
	vector<int>other_vec;
	bool other[11];
	memset(other, true, sizeof(other));

	for (int i = 0; i < v.size(); i++) {
		other[v[i]] = false;
	}

	for (int i = 1; i <= n; i++) {
		if (other[i] == true)
			other_vec.push_back(i);
	}

	return other_vec;
}

// v에 있는 애들 합 구하기
int peoples(vector<int>v)
{
	int sum = 0;
	for (int i = 0; i < v.size(); i++) {
		sum += population[v[i]];
	}
	return sum;
}

void calculate(vector<int>v)
{
	vector<int>v2 = others(v);
	if (possible(v) == true) {
		if (possible(v2) == true) {
			int sum1 = peoples(v);
			int sum2 = peoples(v2);
			if (result > abs(sum1 - sum2)) {
				result = abs(sum1 - sum2);
			}
		}
	}
}

int main()
{
	make_graph();
	for (int r = 1; r <= n / 2; r++)
		make_combinations(r);

	for (int r = 1; r <= n / 2; r++) {
		for (int t = 0; t < comb[r].size(); t++) {
			calculate(comb[r][t]);
		}
	}

	if (result == 987654321)
		cout << -1;
	else
		cout << result;
}