[DFS 2번(조합, 단순), 비트마스킹] (CHECK) 백준 17471 게리맨더링 C++

 

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

17471번: 게리맨더링

#include <bits/stdc++.h>

using namespace std;

int n, ans = INT_MAX, visited, graph[11][11];

int connDfs(int bit, int cnt, int u, int val) {
	int res = val;
	for (int i = 1; i <= n; i++) {
		if ((bit & (1 << i)) == 0) continue; // 확인해야 하는 선거구 아닐 때
		if ((visited & (1 << i)) == (1 << i)) continue; // 이미 방문한 번호
		if (graph[u][i] == 1) { // 인접한 번호
			visited |= (1 << i);
			res += connDfs(bit, cnt + 1, i, graph[i][i]); // += 사용(매개변수, 리턴값 조심)
		}
		if (bit == visited) return res; // 모두 방문 완료
	}
	
	return res;
}

void check(int bit) {
	int a = INT_MAX, b = INT_MAX;

	visited = 0;
	for (int i = 1; i <= n; i++) {
		if ((bit & (1 << i)) == (1 << i)) { // & != &&
			visited |= (1 << i); // 방문 표시
			a = connDfs(bit, 0, i, graph[i][i]);
			break;
		}
	}
	if (bit != visited) return; // 불가능한 경우

	visited = 0;
	bit = (((1 << (n+1)) - 1) ^ bit) - 1; // 1을 0으로, 0을 1로 반전(-1 : 인덱스 1부터 시작), 괄호 조심
	for (int i = 1; i <= n; i++) {
		if ((bit & (1 << i)) == (1 << i)) {
			visited |= (1 << i);
			b = connDfs(bit, 0, i, graph[i][i]);
			break;
		}
	}
	if (bit != visited) return; // 불가능한 경우

	ans = min(ans, abs(a - b));
}

void divideDfs(int bit, int depth, int cnt) {
	if ((cnt > 0 ) && (cnt <= n / 2)) { // 선거구 1개 ~ n/2개까지 확인
		check(bit);
	}

	if (cnt > n / 2) return;
	if (depth > n) return;

	divideDfs(bit | (1 << depth), depth + 1, cnt + 1); // depth번 선택O
	divideDfs(bit, depth + 1, cnt); // depth번 선택X
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n;
	memset(graph, 0, sizeof(graph));
	for (int i = 1; i <= n; i++) {
		cin >> graph[i][i];
	}

	int m, temp;
	for (int i = 1; i <= n; i++) {
		cin >> m;
		for (int j = 1; j <= m; j++) {
			cin >> temp;
			graph[i][temp] = 1;
			graph[temp][i] = 1;
		}
	}

	divideDfs(0, 1, 0);

	if (ans == INT_MAX) ans = -1;
	cout << ans;
}