(C++) - 백준(BOJ) 17471번 : 게리멘더링

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

17471번: 게리맨더링

조합 + union find로 푼 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 n입력 후 일차원 배열 popular에 각 구역의 인구를 입력받습니다.  vector 변수 graph로 간선을 입력받고 인접리스트를 형성합니다.

 

📔 풀이과정

 1. 구역을 2곳로 나누기 : 임의로 나눕니다. 한 쪽의 선거구가 정해진다면 자동으로 나머지 구역들로 선거구가 구성됩니다. 따라서 nCi  (i = 1 ~ n / 2) 만큼 한 쪽 선거구를 조합으로 정해줍니다. 이는 dfs함수로 구현했습니다. 

 

 2. 나눈 구역들로부터 선거구를 정해 명확히 2곳인지 판별하기 : 선거구들이 정해졌다면 한 쪽 선거구에 속한 구역들이 모여있는 ward1, 다른 한 쪽은 ward2라는 vector에 저장합니다. 이 두 선거구가 유효한 선거구인지 union-find로 판별해줍니다. 선거구끼리는 같은 연결 그래프이므로 같은 parent를 가질 수 있도록 union(merge함수) 해줍니다. 그 후 bfs를 수행해서 같은 parent끼리 방문했을 때 해당 선거구를 모두 방문할 수 있다면 선거구가 잘 나눠져있음을 확인할 수 있습니다.

 

 3. 답 정하기 : 두 선거구가 bfs를 수행 후 유효하다고 판별되었을 때 ans의 값과 두 선거구의 차이를 비교해 ans에 저장합니다.

 

📔 정답출력

ans가 INF(0x3f3f3f3f)라면 선거구를 제대로 나눌 수 없다는 의미이므로 -1을 출력합니다. 아니라면 ans를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, popular[11], comb[11], parent[11];
vector <int> graph[11];
int ans = 0x3f3f3f3f;

int find(int x){
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);
    if(a < b) parent[b] = a;
    else parent[a] = b;
}

int bfs(vector <int> ward){
    int ck[11] ={0};
    queue <int> q;
    q.push(ward[0]);
    ck[ward[0]] = 1;

    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(auto next : graph[x]){
            if(ck[next] || parent[next] != parent[x]) continue;
            ck[next] = 1;
            q.push(next);
        }
    }
    for(auto w : ward) if(!ck[w]) return 0;
    return 1;
}

void dfs(int depth, int idx, int range){
    if(depth == range){
        for(int j = 1; j <= n; j++) parent[j] = j;
        vector <int> ward1, ward2;
        int sum1 = 0, sum2 = 0;

        for(int i = 1; i<= n; i++){
            if(comb[i]) ward1.push_back(i), sum1 += popular[i];
            else ward2.push_back(i), sum2 += popular[i];
        }

        for(int i = 0; i < ward1.size() - 1; i++) merge(ward1[i],ward1[i+1]);
        for(int i = 0; i < ward2.size() - 1; i++) merge(ward2[i],ward2[i+1]);
        
        if(bfs(ward1) && bfs(ward2)) ans = min(ans, abs(sum1 - sum2));
        return;
    }
    for(int i = idx; i <= n; i++){
        if(comb[i]) continue;
        comb[i] = 1;
        dfs(depth + 1, i + 1, range);
        comb[i] = 0;
    }
}


int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> popular[i];
    for(int i = 1, edges; i <= n; i++){
        cin >> edges;
        for(int j = 1,v; j <= edges; j++){
            cin >> v;
            graph[i].push_back(v);
            graph[v].push_back(i);
        }
    }

    for(int i = 1; i <= n/2; i++){
        memset(comb,0,sizeof(comb));
        dfs(0,1,i);
    }

    if(ans == 0x3f3f3f3f) cout << -1;
    else cout << ans;
}