17471 게리맨더링

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

17471번: 게리맨더링

 

(풀이)

문제의 조건

1. 각 구역은 두 선거구중 하나에 포함되어야 한다.

2. 각 구역은 모두 연결되어 있어야 한다.

3. 두 구역으로 나누었을때 두 구역의 인구차의 최소값을 구하라.

 

문제의 첫 번째 조건을 만들기 위해 백트래킹을 이용한 조합을 사용하였다.

divide_zone(int cnt, int idx, int limit) check_choice[]의 T구역은 true, F구역은 false로 구분,

두 선거구중 하나에 반드시 포함되어야 하므로 T= N개, F= 0개 이렇게 나오면 안된다.

 

따라서,Check_func()를 하나 만들어서,

구역을 두개의 벡터로 나누었을때 어떤 벡터가 size가 0이된다면,

그것은 두 구역으로 나뉘지 않았다고 판단.

 

다음으로, 1의 조건을 만족하고 2의 조건인 모두 연결되어야 하는 부분은 dfs 함수를 구현

조합으로 선택한 구역과 dfs탐색을 이용하여 방문한 위치가 같은지를 비교하여 검사하였다.

 

마무리 두 조건 (1,2)를 만족 시킬때 인구의 최소값을 구한다. GetPopulation(T구역,F구역)

 

//구역을 두개로 나누고
// 각 구역은 두선거 중 하나에 포함되어야 한다.
// 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 함.
   //인접한 구역 연결, 
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
void Input();
void divide_zone(int cnt, int idx, int limit);
bool check_choice[11];

int check_zone[11];
bool visited[11];
int popu[11];
int N;
vector<int> v[11];
int ans = 987654321;
int Check_func();
bool _t_zone;
bool _f_zone;
void dfs(int node, bool flag);
int GetPopulation(vector<int> &t_zone, vector<int> &f_zone);
int main(void)
{
	Input();
	for (int i = 1; i <= N; ++i)
	{
		divide_zone(0, 1, i);
	}
		
	if (ans == 987654321)
		cout << -1 << '\n';
	else cout << ans << '\n';
	return 0;
}
void dfs(int node,bool flag)
{
	visited[node] = true;
	
	for (int i = 0; i < v[node].size(); ++i)
	{
		int next = v[node][i];

		if (visited[next] == false && check_choice[next] == flag)
		{
			dfs(next, flag);
		}
	}
}
//각 구역의 인구차이 구하기
int GetPopulation(vector<int> &t_zone, vector<int> &f_zone)
{
	int t_sum = 0, f_sum = 0;
	int result_sub = 0;

	for (int i = 0; i < t_zone.size(); ++i)
		t_sum += popu[t_zone[i]];
	for (int i = 0; i < f_zone.size(); ++i)
		f_sum += popu[f_zone[i]];

	result_sub = t_sum - f_sum;

	if (result_sub < 0) result_sub = -result_sub;

	return result_sub;
}
int Check_func()
{
	vector<int> t_zone, f_zone;
	_t_zone = true;
	_f_zone = true;
	for (int i = 1; i <= N; ++i)
	{
		if (check_choice[i]) t_zone.push_back(i);
		else f_zone.push_back(i);
	}
	// 각 구역은 두선거 중 하나에 포함되어야 한다.
	if (t_zone.size() == 0 || f_zone.size() == 0) return false;

	//T 구역 확인
	// 선거구에 포함되어 있는 구역인지 검사.
	dfs(t_zone[0],true);
	// 연결요소가 리스트와 일치하는지 확인
	for (int i = 0; i < t_zone.size(); ++i)
	{
		if (visited[t_zone[i]] == false) 
			_t_zone = false;
	}
	memset(visited, 0, sizeof(visited));
	
	//F 구역 확인
	dfs(f_zone[0],false); //false 인덱스가 true
	for (int i = 0; i < f_zone.size(); ++i)
	{
		if (visited[f_zone[i]] == false) 
			_f_zone = false;
	}
	memset(visited, 0, sizeof(visited));
	// 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 함.
	if (_t_zone == true && _f_zone == true)
	{
		return GetPopulation(t_zone, f_zone);
	}
	else return -1;
}

void divide_zone(int cnt, int idx, int limit)
{
	//선택한 갯수가 limit 개수(1,2,3,4,5,6)
	if (cnt == limit)
	{
		int tmp_sub = Check_func();
		
		//답의 해를 찾은경우
		if (tmp_sub != -1)
		{
			if (ans > tmp_sub)
				ans = tmp_sub;
		}
		return;
	}

	for (int i = idx; i < N; ++i)
	{
		if (check_choice[i] == false)
		{
			check_choice[i] = true;
			divide_zone(cnt + 1, i + 1,limit);
			check_choice[i] = false;
		}
	}

}
void Input()
{
	cin >> N;
	for (int i = 1; i <= N; ++i)
		cin >> popu[i];

	for (int i = 1; i <= N; ++i)
	{
		int n_cnt;
		cin >> n_cnt;
		for (int j = 0; j < n_cnt; ++j)
		{
			int node;
			cin >> node;
			v[i].push_back(node);
		}
	}

}