백준 17371 : 게리맨더링 c++

www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

후기

1. 각 도시별로 연결 여부를 확인하는게 제일 힘들었다.

2. 당연히 queue 써야되는건데 생각이 안나서 vector로 하려다가 쌩고생했다

3. 이렇게 구글링 안하고 기출문제 풀면 기분이 좋다 ㅎㅎ

 

 

풀이는 주석에 친절하게 적혀있지만 그래도 요약하자면

1. n명을 두팀으로 나누는건 '1~ 2/n'명을 1팀, 나머지를 2팀으로 하면된다

2. 조합을 써서 지역 나눈다

3. 지역들끼리 서로 연결이 잘 되어 있나 확인!! ( 팀 가능 여부)

4. 가능하다면 각 지역 인구수 총합을 구하고, 그 차이를 구한다

5. 구한 차이값을 정답과 비교하여, 최솟값을 최종적으로 결과로 출력

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

int people[11];//인구수
int visit[11] = { 0, }; //1~n번노드씀
int visit_2[11] = { 0, };
vector< vector<int> > v(11);
int n;
int answer = 987654321;
int sum_1 = 0;
int sum_2 = 0;
int flag;



void possible()
{
	vector<int> team_1, team_2;
	queue<int> q;
	for (int i = 1; i <= n; i++)
		visit_2[i] = 0;

	for (int i = 1; i <= n; i++)
	{
		if (visit[i] == 0)
			team_1.push_back(i);
		else
			team_2.push_back(i);
	}

	q.push(team_1[0]);
	visit_2[team_1[0]] = 1;
	int count = 1;

	while (!q.empty())//1번 팀
	{
		int a = q.front();
		q.pop();
		for (int i = 0; i < v[a].size(); i++)//나랑 연결된 애들중에!
		{
			if (find(team_1.begin(), team_1.end(), v[a][i]) != team_1.end())//우리 팀이고!
			{
				if (visit_2[v[a][i]] == 0)//아직 queue들간적 없고!
				{
					count++;
					visit_2[v[a][i]] = 1;
					q.push(v[a][i]);
				}
			}
		}
	}

	if (count != team_1.size())//엥 연결안됨!
		flag = 0;


	count = 1;
	q.push(team_2[0]);
	visit_2[team_2[0]] = 1;

	while (!q.empty())//2번 팀
	{
		int a = q.front();
		q.pop();
		for (int i = 0; i < v[a].size(); i++)//연결된 애들중에 우리팀인애들 삽입!
		{
			if (find(team_2.begin(), team_2.end(), v[a][i]) != team_2.end())//우리 팀이고!
			{
				if (visit_2[v[a][i]] == 0)//아직 queue들간적 없고
				{
					count++;
					visit_2[v[a][i]] = 1;
					q.push(v[a][i]);
				}
			}
		}
	}

	if (count != team_2.size())//엥 연결안됨!
		flag = 0;
}

void make_team(int now, int cnt, int size) //조합
{
	if (cnt == size)
	{
		flag = 1;
		possible();
		if (flag ==1 )
		{
			sum_1 = 0;
			sum_2 = 0;
			for (int i = 1; i <= n; i++)
			{
				if (visit[i] == 0)
					sum_1 += people[i];
				else
					sum_2 += people[i];

			}

			answer = min(answer, abs(sum_1 - sum_2));
		}
		return;
	}
	for (int i = now; i <= n; i++)
	{
		if (visit[i] == 0)
		{
			visit[i] = 1;
			make_team(i,cnt + 1, size);
			visit[i] = 0;
		}
	}
}

int main()
{
	int cnt,a;
	cin >> n;
	
	for (int i = 1; i <= n; i++)
		cin >> people[i];

	for (int i = 1; i <= n; i++)
	{
		cin >> cnt;
		for (int k = 0; k < cnt; k++)
		{
			cin >> a;
			v[i].push_back(a);
		}
	}
	// 조합로 팀 나눠!
	// 이 나눈 팀이 가능한지 봐!
	// 가능하면 인구수 차이 계산하고
	// 안되면 패쓰!
	
	for (int i = 1; i <= n/2; i++)//팀 인원수 조합~
	{
		make_team(1, 0,i);
	}

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