게리맨더링(BOJ 17471)

문제

이미지 클릭

문제 설명

• 구역은 1~n번까지 존재하는 데 각 구역에는 특정 인구수가 존재한다.
• 여러 개의 구역을 두 개의 그룹, 즉 선거구로. 분리할 건데 다음 조건을 만족해야 한다.

같은 선거구에 포함된 구역들은 서로 간접 혹은 직접적으로 연결되어야 한다. 

문제 해설

• 저와 같은 경우에는 비트마스크를 활용하여서 완전 탐색을 일차적으로 해주었습니다.

예를 들어 n=6이고 1번과 3번을 같은 그룹으로 만들고 싶다면 000101(2)로 일차적으로 체크해 주고 탐색을 해주면 된다.

• 그런 다음 bfs를 탐색을 해주었는 데 탐색은 일반적인 bfs탐색을 group1과 group2로 따로 나누어서 적용해 주었다.
• 만약 방문 처리 되지 않은 부분이 있다면 그 경우의 수는 생략해 준다.

최종 코드

#include <bits/stdc++.h>
using namespace std;
int n, mn = 1e9 + 7;
vector<int> v[14];
vector<int> d(14);
int solution(int bit) {
    int sum1 = 0, sum2 = 0;
    vector<int> visited(14, 0);
    bool flag1 = false, flag2 = false;
    for (int i = 0; i < n; i++) {
        if (bit & (1 << i)) { #만약 비트값이 1, 즉 선거구1에 포함되는 경우
            sum1 += d[i];
            if (!flag1) { 
            #만약 탐색을 한적이 없다면 탐색 시작(탐색한 적이 있으면 서로 연결 되지 않았다는 것을 의미)
                flag1 = true;
                queue<int> q;
                q.push(i + 1);
                visited[i + 1] = 1;
                while (!q.empty()) {
                    int x = q.front();
                    q.pop();
                    for (auto next : v[x]) {
                        if ((bit & (1 << (next - 1))) && !visited[next]) {
                            visited[next] = 1;
                            q.push(next);
                        }
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (!(bit & (1 << i))) { #비트값이 0, 즉 선거구2에 포함되는 경우
            sum2 += d[i];
            if (!flag2) {
                flag2 = true;
                queue<int> q;
                q.push(i + 1);
                visited[i + 1] = 2;
                while (!q.empty()) {
                    int x = q.front();
                    q.pop();
                    for (auto next : v[x]) {
                        if (!(bit & (1 << (next - 1))) && !visited[next]) {
                            visited[next] = 2;
                            q.push(next);
                        }
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if ((bit & (1 << (i - 1))) && visited[i] != 1) return 1e9 + 7;
        if (!(bit & (1 << (i - 1))) && visited[i] != 2) return 1e9 + 7;
        #방문되지 않았다면 큰 값을 return
    }
    return abs(sum1 - sum2); #차이를 return
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> d[i]; #인구수 입력
    for (int i = 1, x; i <= n; i++) { #연결된 구역을 입력
        cin >> x;
        for (int j = 0, y; j < x; j++) {
            cin >> y;
            v[i].push_back(y);
        }
    }
    for (int i = 1; i < (1 << n) - 1; i++) mn = min(mn, solution(i)); #비트마스크를 활용한 경우의 수
    cout << (mn == 1e9 + 7 ? -1 : mn);
}

이미지 클릭