[백준 17471] 게리멘더링

 

문제 요구사항

저는 dfs+트리 순회?? 비슷 풀이하였습니다.

1. 두 단지로 나누기

2. 단지 연결 확인

3. 단지 합이 최소인지 확인

 

 

1번 풀이

팀 나누는 배열

단순 dfs로 단지를 나누기

 

2번 풀이

방문 배열 선언

1, 0 으로 팀을 나눈뒤, now에서 next로 진행되는데

next가 now랑 같을 경우 진행하는 식으로 연결을 확인

 

3번 풀이

연결 확인이 된다면 1의 합, 0의 합 구한 후 최소 확인

 

다른분 풀이를 보니 bfs로도 풀리는 거 같아 시도

 

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
int n;
int numa[11];
vector<int> v[11];
int visit[11];
int visitv1[11];
int visitv2[11];
int cnt1 = 0;
int cnt2 = 0;
int ans = 987654321;
int flag = 0;
void checkv1(vector<int> go, int a,int b)
{
	cnt1++;
	visitv1[a] = 1;
	for (int i = 0; i < v[a].size(); i++)
	{
		if (visit[v[a].at(i)] == 1)
		{
			if (visitv1[v[a].at(i)] == 0)
			{
				checkv1(go, v[a].at(i), b);
			}
		}
		
	}
}

void checkv2(vector<int> go, int a, int b)
{
	cnt2++;
	visitv2[a] = 1;
	for (int i = 0; i < v[a].size(); i++)
	{
		if (visit[v[a].at(i)] == 0)
		{
			if (visitv2[v[a].at(i)] == 0)
			{
				checkv2(go, v[a].at(i), b);
			}
		}

	}
}
void dfs(int now, int num)
{
	if (num == n + 1)
	{
		vector<int> v1;
		vector<int> v2;
		int num1 = 0;
		int num2 = 0;
		cnt1 = 0;
		cnt2 = 0;
		int ans1 = 0;
		int ans2 = 0;
		for (int i = 1; i <= n; i++)
		{
			if (visit[i] == 1)
			{
				v1.push_back(i);
				num1++;
				ans1 += numa[i];
			}
			else
			{
				num2++;
				v2.push_back(i);
				ans2 += numa[i];
			}
		}
		if (v1.size() > 0 && v2.size() > 0)
		{
			memset(visitv1, 0, sizeof(visit));
			memset(visitv2, 0, sizeof(visitv2));
			checkv1(v1, v1.at(0), 1);
			checkv2(v2, v2.at(0), 1);
		}
		if (num1 == cnt1 && num2 == cnt2)
		{
			flag = 1;
			ans = min(ans, abs(ans1 - ans2));
		}
		return;
	}
	visit[now] = 1;
	dfs(now + 1, num + 1);
	visit[now] = 0;
	dfs(now + 1, num + 1);
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> numa[i];
	}
	char ch;
	cin.get(ch);
	//cout << endl;
	for (int i = 1; i <= n; i++)
	{
		/*
		int j = 0;
		int start = 0;
		while (true)
		{
			char ch;
			cin.get(ch);
			if (ch == '\n')
				break;
			else if (ch == ' ')
				continue;
			if (j == 0)
			{
				start = (int)ch - '0';
				j++;
				continue;
			}
			int a = (int)ch - '0';
		//	cout << a << endl;
			v[a].push_back(start);
			v[start].push_back(a);
		//	cout << "a" << a << "in " << i << endl;
	//		cout << "i" << i << "in " << a << endl;
		}
		*/
		int x;
		cin >> x;
		for (int j = 0; j < x; j++)
		{
			int y;
			cin >> y;
			v[i].push_back(y);
			v[y].push_back(i);
		}
		
	}
	
	dfs(1, 1);
	if (flag == 1)
		cout << ans << endl;
	else
		cout << "-1" << endl;
}