[백준] #17471번 게리맨더링

문제

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

풀이

첫 번째로 생각해야될 것은 구역들을 두 선거구로 어떻게 나눌 것이냐이다. 처음 생각한 것은 1번부터 n번 노드까지 시작 노드로 잡고 dfs를 돌리며 경우의 수를 따질려 했지만, 이 방법은 탐색이 어느 방향으로 갈지 모르므로 모든 경우의 수를 탐색하지 못했다. 결국은 조합을 사용해야 한다. 즉, 1~n-1까지 조합을 돌린 수열을 A선거구, A선거구를 제외한 수열을 B선거구로 잡고, 시작하면 된다.

두 번째로 생각해야될 것은 A선거구와 B선거구에 포함된 구역들이 서로 인접해있는지 체크하는 것이다. (위 그림 참조) 이 부분에서 어떻게 수열이 인접해 있는지 확인할까에 대해 고민이 많았는데 조합 구현 과정에서 인덱스 노드가 어느 선거구에 속하는지 char 배열로 관리해줌으로써 해결할 수 있었다. (또는 분리집합을 이용해 두 개의 parent로 구분해줄 수도 있다) (그러면 해당 선거구에 포함된 구역들의 탐색이 수월해진다)

마지막으로 BFS 탐색을 수행하면서 선거구에 포함된 구역들의 갯수를 구하고, 두 선거구의 총 합이 N일 때 정답을 갱신시키면 된다. 조합과 BFS를 사용하면 O(N*2^N) (N<=10)이므로 시간제한 안에 구현 가능하다.

코드

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

using namespace std;

/*
	조합으로 가능한 각 세션을 구하고, bfs로 이어지는지 확인
	그리고 인구수 구함 
*/

int n;
int answer = 987654321;
int population[11];
vector<int> v[11];
char section[11];
int populationA, populationB;

int bfs(int start, char target){
	int cnt = 1;
	queue<int> q;
	bool visited[11];
	memset(visited, false, sizeof(visited));
	
	q.push(start);	
	visited[start] = true;
	
	while(q.size()){
		int cnode = q.front(); q.pop();
		
		for(int i = 0; i < v[cnode].size(); i++){
			int nnode = v[cnode][i];
			if(!visited[nnode] && section[nnode] == target){
				cnt++;
				visited[nnode] = true;
				q.push(nnode);
				
				if(target == 'A') populationA += population[nnode];
				else populationB += population[nnode];
			}
		}
	}
	
	return cnt;
}

void comb(int limit, int cnt, int idx){
	if(limit == cnt){
		
		int sectionA, sectionB;
		
		for(int i = 1; i <= n; i++){
			if(section[i] != 'A'){
				section[i] = 'B';
				sectionB = i;
			}else{
				sectionA = i;	
			}
		}
		
		populationA = population[sectionA], populationB = population[sectionB];
		
		int sum = bfs(sectionA, 'A') + bfs(sectionB, 'B');
		
		if(sum == n){
			answer = min(answer, abs(populationA - populationB));		
		}
		
		return;	
	}
	
	for(int i = idx; i <= n; i++){
		section[i] = 'A';
		comb(limit, cnt + 1, i + 1);
		section[i] = 'B';
	}
}

int main(){
	cin >> n;
		
	for(int i = 1; i <= n; i++){
		cin >> population[i];	
	}
	
	for(int i = 1; i <= n; i++){
		int t; cin >> t;
		while(t--){
			int u; cin >> u;
			v[i].push_back(u);		
		}
	}
	
	for(int i = 1; i < n; i++){
		comb(i, 0, 1);	
	}

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