BOJ 17471 - 게리맨더링(완전탐색, dfs)

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

17471번: 게리맨더링

- 노드의 갯수(도시 갯수)가 작기 때문에 도시들을 두 팀으로 나누는 모든 경우의 수를 비트마스킹으로 탐색해 나간다.

그리고 dfs를 통해서 나눠진 팀들(선거구)끼리 한 지점으로부터 모두 순회할 수 있는지를 체크하는데 파라미터로 팀원수, 같은 팀인지 여부를 계속 넘겨주면서 계속 탐색해나간다. 만약 두 팀의 팀원수 합이 전체 노드갯수가 많거나 작지 않고 n개이면 두 팀 간의 인구 차이를 ans에 계속 비교해나가면서 풀어주면 된다. 

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)
#define INF 987654321

// 두 선거구 인구차이의 최솟값, 못나누면 -1
int n, ans = INF;  // 도시갯수10
int p[11];         //  인구100
vector<int> graph[11];
bool check[11];  // 방문여부
bool which[11];  // team0, team1 구분

pii dfs(int now, bool team) {
    check[now] = true;

    pii ret = {1, p[now]};
    for (int n : graph[now]) {
        if (which[n] != team || check[n]) continue;

        pii next = dfs(n, team);
        ret.first += next.first;
        ret.second += next.second;
    }

    return ret;
}

int main() {
    FASTIO;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }

    for (int u = 1; u <= n; ++u) {
        int n, v;
        cin >> n;
        for (int j = 0; j < n; ++j) {
            cin >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
    }

    for (int i = 1; i < (1 << n) - 1; ++i) {  // 000001~111110 까지 체크
        memset(check, false, sizeof(check));
        memset(which, false, sizeof(which));

        int s1, s2;
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                which[j + 1] = true;
                s1 = j + 1;
            } else {
                s2 = j + 1;
            }
        }

        pii team1 = dfs(s1, 1);
        pii team2 = dfs(s2, 0);
        if (team1.first + team2.first == n) {
            ans = min(ans, abs(team1.second - team2.second));
        }
    }

    cout << (ans == INF ? -1 : ans);
    return 0;
}