17471번 게리맨더링

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

 

공부겸 오랜만에 풀어본 문제다.

 

#include <bits/stdc++.h>

using namespace std;

/*
1. 두 선거구로 나누기 - 백트래킹
2. 각 선거구 내 구역들이 인접한지 check - bfs
3. 모두 인접해있다면, 두 선거구의 총인구합 구하기 - 구현
*/

int N, person[11]; // person[i] : i번째 구역 인구 수
int ans = 2e9;
vector<int> v[11];
bool used[11], num[11];

bool chk(vector<int> a, vector<int> b) {
    memset(used, false, sizeof(used));

    queue<int> q;
    used[a[0]] = true;
    q.push(a[0]);

    // a선거구 내에서만 움직여야 하므로, 미리 b선거구를 방문 처리 표시한다.
    // 그래서 a선거구에서 b선구로갔다가 다시 a선거구로 가는 경우를 막는다.
    for (auto i : b) {
        used[i] = true;
    }

    while (!q.empty())
    {
        int qs = q.size();

        while (qs--)
        {
            int now = q.front();

            q.pop();

            for (auto next : v[now]) {
                if (!used[next]) {
                    used[next] = true;
                    q.push(next);
                }
            }
        }
    }

    for (auto i : a) {
        if (!used[i]) {
            return false;
        }
    }

    return true;
}

void bt(vector<int> & a, int st) {
    if (!a.empty() && a.size() != N) {
        vector<int> b;
        for (int i = 1; i <= N; i++) {
            if (!num[i]) {
                b.push_back(i);
            }
        }

        /*printf("■■■■■■■■■■■■■\n");
        for (auto i : a) printf("%d ", i);
        printf("\n");

        for (auto i : b) printf("%d ", i);
        printf("\n");
        printf("■■■■■■■■■■■■■\n");*/

        if (chk(a, b) && chk(b, a)) {
            int sa = 0, sb = 0;
            for (auto i : a) sa += person[i];
            for (auto i : b) sb += person[i];
            ans = min(ans, abs(sa - sb));
        }
    }

    for (int i = st; i <= N; i++) {
        a.push_back(i);
        num[i] = true;

        bt(a, i + 1);

        num[i] = false;
        a.pop_back();
    }
}

int main()
{
    cin.tie(0);

    scanf("%d", &N);

    for (int i = 1; i <= N; i++) {
        scanf("%d", &person[i]);
    }

    for (int i = 1; i <= N; i++) {
        int cnt = 0;
        scanf("%d", &cnt);
        for (int j = 0; j < cnt; j++) {
            int vilg = 0;
            scanf("%d", &vilg);
            v[i].push_back(vilg);
        }
    }

    vector<int> a;

    bt(a, 1);

    printf("%d\n", ans == 2e9 ? -1 : ans);

    return 0;
}