백준 17471_게리맨더링(C++)

 

www.acmicpc.net/problem/17471

17471번: 게리맨더링

[문제 풀이]

브루트 포스(Brute force)를 이용하여 문제를 풀었습니다.

 

이 문제는 주어진 입력을 두 집합으로 나누었을 때 나누어진 집합이 그래프로 연결 되어 있는지를 찾는 문제였습니다. 예를 들어 두 집합 A ={ 1, 2, 3 }, B = { 4, 5, 6 }으로 나누었을 때 A의 노드들이 A의 노드를 통해서 모두 연결 되어 있어야 합니다. 반대로 B 또한 마찬가지입니다.

 

파란색 집합의 원소 5가 B의 노드를 통해 6으로 갈 수 없으므로 아래의 그림은 불가능한 방법입니다.

 

 

또한, 두 집합 중 한 집합이라도 공집합이면 안됩니다.

 

 

로직 설명

• 도시를 두 구역으로 나눕니다.
• 나누어진 구역끼리 연결 되어 있는지 확인합니다.
• 연결 되어 있다면 값을 비교해 줍니다.

[코드]

#include<iostream>
#include<math.h>

using namespace std;

int N, answer = 987654321;

int population[11] = { 0, };
int map[11][11] = { 0, };
int visit[11] = { 0, };
int connect_city[11];

void Connect(int idx, int check) {//도시 연결

	for (int j = 1; j <= N; j++)
		if (map[idx][j] == 1 && visit[j] == check && connect_city[j] == 2) {
			connect_city[j] = check;
			Connect(j, check);
		}


}

bool ConnectCheck() {//도시 연결 여부 확인

	for (int i = 1; i <= N; i++)
		connect_city[i] = 2;

	for (int i = 1; i <= N; i++)
		if (visit[i] == 1) {
			connect_city[i] = 1;
			Connect(i, 1);
			break;
		}

	for (int i = 1; i <= N; i++)
		if (visit[i] == 0) {
			connect_city[i] = 0;
			Connect(i, 0);
			break;
		}

	for (int i = 1; i <= N; i++)
		if (connect_city[i] != visit[i])
			return false;

	return true;

}

void Divide(int num, int total, int a_total) {

	if (num == total) {
		if (ConnectCheck()) {//인구 수 비교
			int b_total = 0;

			for (int i = 1; i <= N; i++)
				if (visit[i] == 0)
					b_total += population[i];

			if (answer > abs(a_total - b_total))
				answer = abs(a_total - b_total);

		}
		return;
	}

	for (int i = 1; i <= N; i++) {

		if (visit[i] == 0) {

			visit[i] = 1;
			Divide(num + 1, total, a_total + population[i]);
			visit[i] = 0;

		}

	}

}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	for (int i = 1; i <= N; i++) 
		cin >> population[i];

	for (int i = 1; i <= N; i++) {
		int number; cin >> number;

		for (int j = 0; j < number; j++) {
			int temp; cin >> temp;

			map[i][temp] = 1;
		}
	}

	for (int i = 1; i <= N / 2; i++) //도시 나누기
		Divide(0, i, 0);

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

	return 0;

}