백준 17471 - 게리맨더링(골드4)

문제

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

접근법

일단 N의 개수가 작아서 나누는 방법을 일일히 해봐도 괜찮을 것 같다는 생각이 들었다.
그래서 조합 알고리즘을 사용해 두 구역으로 일일히 나눴다.
(한쪽으로 몰리는 경우 제외)

그 후 dfs를 돌려 같은 구역끼리 붙어있는 지 검사했다.
이 때 중요한 것은 중간에 나눠지는 경우, 즉 빨강-파랑-빨강
이런 식으로 되는 것은 불가능한 방법이므로 유의해야한다.

조건에 만족했다면 두 인구수 차이의 값을 갱신한다.

구현

#include <stdio.h>
#include <vector>
#include <string.h>
#include <math.h>
#include <algorithm>
#define INF 987654321
using namespace std;
int n;
vector<int> list[11];
int population[11];
vector<int> red;

int d[11];
int visit[11];
int ans=INF;
void dfs(int s)
{
	visit[s]=1;
	vector<int>::iterator it;
	for(it=list[s].begin();it!=list[s].end();it++)
	{
		if(!visit[*it] && d[*it]==d[s])
		{
			dfs(*it);
		}
	}
}
void divi(int depth,int end)
{
	if(depth==end)
	{
		
		memset(d,0,sizeof(d));
		
		for(int i=0;i<red.size();i++)
		{
			d[red[i]]=1;
		}
		
		for(int i=1;i<=n;i++)
		{
			if(d[i]==1)
			{
				memset(visit,0,sizeof(visit));
				dfs(i);
				
				for(int r=0;r<red.size();r++)
				{
					if(!visit[red[r]])
						return;
				}
			}
			else
			{
				memset(visit,0,sizeof(visit));
				dfs(i);
				for(int j=1;j<=n;j++)
				{
					if(d[j]==0)
					{
						if(!visit[j])
							return;
					}
				}
			}
			
		
			
		}
		
		int redsum=0;
		int bluesum=0;
		for(int i=1;i<=n;i++)
		{
			if(d[i]==1)
			{
				redsum+=population[i];
			}
			else
			{
				bluesum+=population[i];
			}
		}
		ans=min(ans,abs(redsum-bluesum));
	}
	else
	{
		divi(depth+1,end);
		
		red.push_back(depth+1);
		divi(depth+1,end);
		red.pop_back();
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&population[i]);
	}
	for(int i=1;i<=n;i++)
	{
		int num;
		scanf("%d",&num);
		for(int j=0;j<num;j++)
		{
			int next;
			scanf("%d",&next);
			list[i].push_back(next);
			list[next].push_back(i);
		}
	}
	divi(0,n);
	if(ans==INF)
		printf("-1");
	else
		printf("%d",ans);
	return 0;
}

조금 비효율적으로 구현한 감이 없지 않아 있다.