[BeakJoon 17471] 게리맨더링

안녕하세요. 오늘은 백준 17471 게리맨더링 문제를 풀어보도록 하겠습니다.

 

해당 문제는 

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

17471번: 게리맨더링

 

위 링크에서 확인하실 수 있습니다.

 

 

저는 다음과 같은 순서로 이 문제를 해결하였습니다.

 

1. 정해진 N의 개수만큼 두 집단으로 분리 

2. 분리되었다면 각각 연결되어 있는지 확인

3. 올바르게 분리 되었다면, 결과 갱신

 

1을 위해 저는 각 함수마다 두 개의 재귀 함수를 호출하여 주었습니다. 

각각 group을 A, B라 한다면 현재 idx의 노드가 A에 들어갈 경우, B에 들어갈 경우를 분리하여 재귀를 호출해주었습니다.

 

그다음 idx 가 N을 넘어갔다면, 모든 노드에 대한 분할이 완료되었다는 뜻이므로, 각 그룹이 모두 연결되어 있는지 확인했습니다. 해당 구현은 BFS를 통해 확인하였습니다.

 

두 집단 모두 정상적으로 연결되었다면, 최솟값을 갱신해 주었습니다.

 

* 추가로 그룹 분할의 케이스를 빠르게 진행하기 위해 비트마스킹을 활용하였습니다.

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;

int n, res=99999999;
int people[14], visited[14];
vector<int> graph[14];

bool check(int group) {
	fill(visited, visited+14, 1);
	int start = 1;
	for(int i = 1; i <= n; i++) {
		if(group&(1<<i)) visited[i] = 0, start=i;	
	}
	
	queue<int> q;
	q.push(start);
	visited[start] = 1;
	
	while(q.size()) {
		int here = q.front(); q.pop();
		
		for(int there : graph[here]) {
			if(!visited[there]) {
				visited[there] = 1;
				q.push(there);
			}
		}
	}
	
	for(int i = 0; i < 14; i++) if(visited[i] == 0) return false;
	return true;
}
int calc(int a, int b) {
	int ret1 = 0, ret2 = 0;
	for(int i = 1; i <= n; i++) 
		if(a&(1<<i)) ret1+=people[i];
		else if(b&(1<<i)) ret2+=people[i];
	
	return abs(ret2 - ret1);
}
void go(int idx, int groupA, int groupB) {
	if(idx > n) {
		if(check(groupA) && check(groupB)) res = min(res, calc(groupA, groupB));
		return;	
	}
	
	go(idx+1, groupA|(1<<idx), groupB);
	go(idx+1, groupA, groupB|(1<<idx));
	return;
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	
	for(int i = 1; i <= n; i++) cin >> people[i];
	for(int i = 1; i <= n; i++) {
		int a; cin >> a;
		for(int j = 0; j < a; j++) {
			int v; cin >> v;
			graph[i].push_back(v);
		}
	}
	
	go(1, 0, 0);
	if(res!=99999999) cout << res;
	else cout << -1;
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.