백준 17471문제

#include <bits/stdc++.h>
using namespace std;

int N, pop[12],visit[12],divi[12],ANS = 1e9;
vector<vector<int>> G;

void dfs(int cur, int division){
    visit[cur] = 1;

    for(int next : G[cur])
        if(!visit[next] && divi[next] == division)
            dfs(next, division);
}

void update(){
    int div0 = -1, div1 = -1;

    for(int i=0 ;i<N ;i++)
        if(divi[i] == 0) div0 = i;
        else div1= i; 

    if(div0 != -1 && div1 != -1){
        dfs(div0, 0) , dfs(div1,1);
        bool flag = true;
        for(int i=0 ; i<N ; i++) if(!visit[i]) flag = false;
        if(flag){
            int pop0 = 0, pop1 = 0;
            for(int i=0 ;i<N;i++) if(divi[i] == 0) pop0 += pop[i];
            for(int i=0 ;i<N;i++) if(divi[i] == 1) pop1 += pop[i];
            ANS = min(ANS, abs(pop0 - pop1));
        }
    }
    memset(visit, 0 , sizeof(visit));
}

void div(int cur){ 
    if(cur >= N){
        update();
        return;
    }

    divi[cur] = 1;
    div(cur + 1);
    divi[cur] = 0;
    div(cur + 1);
}

int main(){
    cin >> N;
    G.resize(N);

    for(int i=0; i<N ; i++) cin >> pop[i];

    for(int i=0; i<N ; i++){
        int k; cin >> k;
        for(;k>0;k--){
            int p; cin >> p;
            G[i].push_back(p-1);
        }
    }

    div(0);

    cout << (ANS == 1e9 ? -1 : ANS) << endl;

    return 0;
}

백준 게리맨더링 문제 풀이입니다.