[17471] 게리맨더링

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

17471번: 게리맨더링

<문제>

for(int bt=0; bt<(1<<n); bt++)로 n개중의 조합을 브루트포스하게 탐색할 수 있다.

(어느 한쪽이) 공집합인 경우는 무의미한 문제이므로, 양쪽으로 탐색범위를 한칸씩 옮겨주거나

builtin_popcount(bt)으로 비트내 1의 수를 세고, 이것이 n혹은 0일때 return하면 되겠다.

 

 

2번, 각 구역중 아무거나 하나 잡고 탐색을 진행한 다음 모든 노드를 방문했다면 정답을 업데이트해준다.

 

 

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int n, score[2], ans = INF, a[11];
bool vst[11], check[11];
vector<int> adj[11];
int f(int cur, int bt) {
    int ret = 1;
    vst[cur] = true;
    score[check[cur] == true ? 0 : 1] += a[cur];
    for (int next : adj[cur]) {
        if (check[cur] != check[next]) continue;
        if (vst[next] == false) {
            vst[next] = true;
            ret += f(next, bt);
        }
    }
    return ret;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int i, j;
    for (i = 0; i < n; i++) cin >> a[i];
    for (i = 0; i < n; i++) {
        int S;
        cin >> S;
        for (j = 0; j < S; j++) {
            int x;
            cin >> x;
            x--;
            adj[i].push_back(x);
            adj[x].push_back(i);
        }
    }
    int S = (1 << n) - 1;
    for (i = 1; i < S; i++) {
        int redIdx, blueIdx;
        memset(score, 0, sizeof(score));
        memset(check, 0, sizeof(check));
        memset(vst, 0, sizeof(vst));
        for (j = 0; j < n; j++) {
            if (i & (1 << j)) {
                check[j] = true;
                redIdx = j;
            } else {
                blueIdx = j;
            }
        }
        int ret = f(redIdx, i) + f(blueIdx, i);
        if (ret == n) ans = min(abs(score[1] - score[0]), ans);
    }
    if (ans == INF) ans = -1;
    cout << ans;
    return 0;
}