[C++] 백준 - 17471 : 게리맨더링

문제 링크

17471번: 게리맨더링

 

 

풀이 )

  1번 도시를 포함한 선거구 v1, 1번 도시를 포함하지 않은 선거구 v2로 나누었다. 이때 나눌때는 완전탐색을 했다.

  이후 나눈 두 선거구가 가능한지 여부를 BFS를 사용해서 확인해서 가능한 경우, 두 선거구의 인원수 차이를 갱신한다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n;
int total_pop = 0;
int popul[10];
bool adj[10][10];
vector<int> v1;
vector<int> v2;
vector<int> tmp1(1);	// v1 초기화용
vector<int> tmp2;		// v2 초기화용
int ans = 1e9;

bool check(vector<int> v){
    int len = v.size();
    if(len == 1)		// 도시가 1개일 경우 반드시 가능
        return true;

    vector<bool> vb(len);
    queue<int> q;
    q.push(v[0]);
    vb[0] = true;

    while(!q.empty()){		// BFS로 선거구 도시 방문
        int cur = q.front();
        q.pop();
        for(int i = 1; i < len; ++i){
            if(!vb[i] && adj[cur][v[i]]){
                q.push(v[i]);
                vb[i] = true;
            }
        }
    }

    for(int i = 0; i < len; ++i)
        if(!vb[i])
            return false;
    return true;	// 모든 도시 방문 했는지
}

void divide(int pos, int cnt, int target){
    if(cnt == target){
        v2 = tmp2;
        int len = v1.size();
        int city = 1;
        int cur = 1;
        while(1){		// v1 선거구를 이용해 나머지 도시를 v2 선거구로
            if(city == n)
                break;
            if(cur == len || city < v1[cur])
                v2.push_back(city);
            else
                cur++;
            city++;
        }
        if(check(v1) && check(v2)){		// 두 선거구 가능
            int len = v1.size();
            int v1Sum = 0;
            for(int j = 0; j < len; ++j)
                v1Sum += popul[v1[j]];

            if(abs(total_pop-2*v1Sum) >= ans)
                return;
            ans = abs(total_pop-2*v1Sum);
        }
        return;
    }

    for(int i = pos; i < n; ++i){		// 완전탐색으로 v1 선거구 도시 선택
        v1.push_back(i);
        divide(i+1, cnt+1, target);
        v1.pop_back();
    }
}

int main(void){
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> popul[i];
        total_pop += popul[i];
    }

    for(int i = 0; i < n; ++i){
        int num;
        cin >> num;
        while(num--){
            int city;
            cin >> city;
            adj[i][city-1] = true;
            adj[city-1][i] = true;
        }
    }

    for(int i = 1; i < n; ++i){
        v1 = tmp1;
        v2 = tmp2;
        divide(1, 1, i);
    }

    if(ans == 1e9)
        ans = -1;
    cout << ans << '\n';
    return 0;
}