백준 17471번 게리맨더링

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

17471번: 게리맨더링

 

 

 

 

 

<접근방법>

완전탐색 문제입니다.

정점을 선택한 후에 연결여부를 확인해야합니다.

 

선택은 백트래킹으로 하면 됩니다.

정점 선택은 조합으로 해야겠죠.

그럼 자연스레 2개의 그룹으로 나뉩니다.

 

확인은 bfs로 하면 됩니다.

2개의 그룹 모두 확인 해야합니다.

하나의 그룹이 모두 연결되어 있다고해도 다른 그룹은 아닐 수 있으니까요.

 

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int INF = 987654321;
int n, w[10];
bool map[10][10], a[10], alone[10];
int lim, res = INF;

bool check1() {
	queue<int> q;
	bool visit[10] = { false, };

	for (int i = 0; i < n; i++) {
		if (a[i]) {
			q.push(i);
			visit[i] = true;
			break;
		}
	}

	while (!q.empty()) {
		int now = q.front();
		q.pop();

		for (int i = 0; i < n; i++) {
			if (map[now][i]) {
				int next = i;
				if (visit[next] || !a[next]) continue;

				q.push(next);
				visit[next] = true;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		if (a[i]) {
			if(!visit[i]) return false;
		}
		if (!a[i]) {
			if (visit[i]) return false;
		}
	}
	return true;
}

bool check2() {
	queue<int> q;
	bool visit[10] = { false, };

	for (int i = 0; i < n; i++) {
		if (!a[i]) {
			q.push(i);
			visit[i] = true;
			break;
		}
	}


	while (!q.empty()) {
		int now = q.front();
		q.pop();

		for (int i = 0; i < n; i++) {
			if (map[now][i]) {
				int next = i;
				if (visit[next] || a[next]) continue;

				q.push(next);
				visit[next] = true;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		if (a[i]) {
			if (visit[i]) return false;
		}
		if (!a[i]) {
			if (!visit[i]) return false;
		}
	}
	return true;
}

int cal() {
	int A=0, B=0;
	for (int i = 0; i < n; i++) {
		if (a[i]) {
			A += w[i];
		}
		else {
			B += w[i];
		}
	}

	return abs(A-B);
}

void dfs(int dep, int start) {
	if (dep == lim) {
		if (check1()) {
			if (check2()) {
				res = min(res, cal());
			}
		}
		return;
	}

	for (int i = start; i < n; i++) {
		a[i] = true;
		dfs(dep+1, i+1);
		a[i] = false;
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> w[i];
	}
	for (int i = 0, a; i < n; i++) {
		cin >> a;
		for (int j = 0, b; j < a; j++) {
			cin >> b;
			map[i][b-1] = true;
		}
	}

	for (int i = n - 1; i >= 1; i--) {
		lim = i;
		dfs(0, 0);
	}

	if (res == INF) cout << -1 << '\n';
	else cout << res << '\n';

	return 0;
}