[C++, DFS, Bitmask] 백준 17471번 게리맨더링 문제풀이

문제

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

17471번: 게리맨더링

해설

비트마스크라는 참신한 풀이법을 익힌 문제이다. 그래프 문제에서 유용하게 쓰일 수 있는 기법을 발견했다. 

선거구 즉, 총 노드의 개수만큼 비트를 할당하여 방문할 노드 선정하는 방법이다.

코드에서 i는 노드에 방문할 총 가짓수를 나타내고 j는 실제 방문한 노드를 나타내어 dfs기법으로 각 노드를 탐색한다.

여기서 특정할 만한 건 i를 반전시켜 2개로 나눈 그룹의 인구를 다시 빼준다는 것이다.

끝에 모두 방문했는지 확인하는 절차가 필요하다. 

2개의 그룹으로만 나누어질때 사용할 수 있을 것 같다.

참고로 2e9은 2*10^9(20억)을 나타낸다.

 

비트마스크를 좀 더 자세히 알아보고 싶다면 

• https://m.blog.naver.com/kks227/220787042377

 

C++에서 비트마스크를 이용해 문제풀이를 할 경우 디버그시 유용한 헤더 파일이다.

int형을 2진수로 바꾸어 표현해준다.

• https://en.cppreference.com/w/cpp/header/bitset

Standard library header - cppreference.com

//bitset<표현할 비트 수>(표현할 수)
#include <bitset>
int main(){
    for(int i=1;i<=10;i++)
         cout<<bitset<6>(i)<<"\n"
}
//result
//000001
//000010
//000011
//000100
//000101
//000110
//000111
//001000
//001001
//001010

풀이 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <bitset>
 
using namespace std;
int n, a[11],adj[11][11],c[11],sum,ans=2e9;
int dfs(int x, int bm){
    int res = a[x];
    c[x] = 1;
    for (int i = 0; i < n; ++i){
        if (adj[x][i + 1] && (bm & (1 << i)) && !c[i + 1])
            res += dfs(i + 1, bm);
 
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1, t; i <= n; ++i){
        cin >> t;
        for (int j = 0, tmp; j < t; j++){
            cin >> tmp;
            adj[i][tmp] = 1;
        }
    }
    for (int i = 1, j; i < 1 << n; ++i){
        memset(c, 0, sizeof(c));
        sum = 0;
        for (j = 0; j < n; ++j){
            if (i&(1 << j)){
                sum = dfs(j + 1, i);
                break;
            }
        }
        for (j = 0; j < n; ++j){
            if (~i&(1 << j)){
                sum -= dfs(j + 1, ~i);
                break;
            }
        }
        j = 1;
        while (j <=n&&c[j])j++;
        if (j > n){ 
            ans = min(ans, abs(sum));
        }
    }
    cout << (ans == 2e9 ? -1 : ans);
    return 0;
}