[백준/BOJ] 백준 17471번 : 게리맨더링

www.acmicpc.net/problem/17471

17471번: 게리맨더링

vector<int> check(11, 0); 를 이용해 a선거구와 b선거구로 나누었는데, check[1] ~ check[n]까지 1로 체크될 수 있는 모든 경우의 수를 확인해, 1로 체크된 수는 a선거구, 나머지는 b선거구로 나누었다. 이렇게 나눈 선거구가 두 선거구로 나누어질 수 있는 경우인지를 확인하고, 나누어 질 수 있는 경우일 때 두 선거구의 인구 차이를 구하는 방법을 통해 두 선거구 인구 차이의 가장 작은 값을 찾았다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdlib>
using namespace std;

int n;
int people[11];
vector<int> adj[11];
int discovered[11];
int result = 987654321;

void Pre()
{
	for (int i = 0; i < 11; i++)
		discovered[i] = 0;
}

//check(1:a선거구, 0:b선거구)로 나눈 선거구가 가능한 방법인지 확인
bool connectCheck(vector<int>& check)
{
	vector<int> a_area;
	vector<int> b_area;

	for (int i = 1; i <= n; i++)
	{
		if (check[i] == 1)
			a_area.push_back(i); //a 선거구
		else
			b_area.push_back(i); //b 선거구
	}

	//a선거구 또는 b선거구의 구역이 없을때
	if (a_area.size() == 0 || b_area.size() == 0)
		return false;


	//a선거구의 각 구역이 연결되어 있는지 bfs를 통해 확인한다

	Pre(); //discovered 초기화
	int a_start = a_area[0];
	queue<int> a_q;

	discovered[a_start] = 1;
	a_q.push(a_start);

	while (!a_q.empty())
	{
		int a_here = a_q.front();
		a_q.pop();

		for (int i = 0; i < adj[a_here].size(); i++)
		{
			int a_there = adj[a_here][i];

			//a_there가 a선거구이고, 발견된적이 없을때
			if (check[a_there] == 1 && discovered[a_there] == 0)
			{
				discovered[a_there] = 1;
				a_q.push(a_there);
			}
		}
	}


	//b선거구의 각 구역이 연결되어 있는지 bfs를 통해 확인한다

	int b_start = b_area[0];
	queue<int> b_q;

	discovered[b_start] = 1;
	b_q.push(b_start);

	while (!b_q.empty())
	{
		int b_here = b_q.front();
		b_q.pop();

		for (int i = 0; i < adj[b_here].size(); i++)
		{
			int b_there = adj[b_here][i];

			//b_there가 b선거구이고, 발견된적이 없을때
			if (check[b_there] == 0 && discovered[b_there] == 0)
			{
				discovered[b_there] = 1;
				b_q.push(b_there);
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		//a선거구에 연결되지 않은 구역이 있을때
		if (check[i] == 1 && discovered[i] == 0)
			return false;

		//b선거구에 연결되지 않은 구역이 있을때
		if (check[i] == 0 && discovered[i] == 0)
			return false;
	}

	return true;
}

void Solve(vector<int>& check, int before_check)
{
	if (connectCheck(check)) //선거구로 나눈 방법이 가능할때
	{
		int a_num = 0;
		int b_num = 0;

		for (int i = 1; i <= n; i++)
		{
			if (check[i] == 1)
				a_num += people[i]; //a선거구 인구
			else
				b_num += people[i]; //b선거구 인구
		}

		result = min(result, abs(a_num - b_num));
	}

	//중복된 선택을 막기위해 이전에 체크한 번호보다 큰 수만 고른다
	//check에 1로 체크된 수는 a선거구, 나머지는 b선거구
	for (int i = before_check + 1; i <= n; i++)
	{
		check[i] = 1;

		Solve(check, i);

		check[i] = 0;
	}
}

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

	int people_num;
	int adj_num;
	int number;

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> people_num;
		people[i] = people_num;
	}

	for (int i = 1; i <= n; i++)
	{
		cin >> adj_num;

		for (int j = 0; j < adj_num; j++)
		{
			cin >> number;
			adj[i].push_back(number);
		}
	}

	vector<int> check(11, 0);

	Solve(check, 0);

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

	else
		cout << result;

	return 0;
}