BOJ 17471 : 게리맨더링

문제링크

풀이요약

비트마스킹, DFS

풀이상세

1. $N$ 의 최댓값은 $10$ 이므로 모든 경우의 수를 탐색하는 것이 가능하다.

2. $2^{10}$ 에서 나오는 모든 경우의수를 비트마스킹화 하여, 모든 인덱스와 비교한다. 경우의 수에 해당 인덱스가 존재하면 a , 존재하지 않으면 b 로 나눈다. 현재 상황에서 각 인덱스가 어느 구역인지를 저장하기 위해, 맵을 사용했다.

3. 나누어진 a 와 b 구역을 탐색한다. 동일한 구역이면서 아직 방문처리 되지 않은 노드를 모두 찾는다. 현재 구역의 총 갯수를 반환하게 하여, 만약 a+b 노드의 갯수가 $N$ 과 동일하다면 현재 나눈 구역 배치는 인구수를 구하는 것이 가능한 방법에 해당되는 것이다.

4. 이 때, 각각의 구역에 총합을 찾아 a,b 총합 간의 차의 절댓값을 현재까지의 최소의 값과 계속 비교한다.

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;
int N;
vector<int> v[10], p, visited;
unordered_map<int, char> m;
const int INF = 987654321;
int ans = INF;
int a, b, sta, stb, sum_a, sum_b;
void input() {
    cin >> N;
    int num;
    for (int i = 0; i < N; i++) {
        cin >> num;
        p.push_back(num);
    }

    int n;
    for (int i = 0; i < N; i++) {
        cin >> n;
        int node;
        for (int j = 0; j < n; j++) {
            cin >> node;
            v[i].push_back(node - 1);
        }
    }
}

int check(int node, char t) {
    visited[node]++;
    int ret = 1;
    for (auto n: v[node]) {
        if (m[n] != t || visited[n]) continue;
        ret += check(n, t);
    }
    return ret;
}

void solve() {
    for (int i = 1; i < (1 << N) - 1; i++) {
        a = b = 0;
        sta = stb = -1;
        visited = vector<int>(N, 0);
        for (int j = 0; j < N; j++) {
            if (i & (1 << j)) {
                m[j] = 'a', a++;
                sta = j;
            } else {
                m[j] = 'b', b++;
                stb = j;
            }
        }

        if ((check(sta, 'a') + check(stb, 'b')) == N) {
            sum_a = sum_b = 0;
            for (int j = 0; j < N; j++) {
                if (m[j] == 'a') sum_a += p[j];
                else sum_b += p[j];
            }
            ans = min(ans, abs(sum_a - sum_b));
        };
    }
}

void output() {
    cout << (ans == INF ? -1 : ans);
}

int main() {
    input();
    solve();
    output();
}