게리맨더링( BOJ 17471 )

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

17471번: 게리맨더링

 

문제 파악하기

입력된 그래프를 2개의 구역으로 나눠 인구수의 차이를 최소로 하는 경우를 찾는 문제입니다. 마을의 개수(N)이 작기 때문에 모든 경우의 수를 탐색해도 충분한 문제입니다. 각각의 마을을 0번 혹은 1번 선거구로 설정한 다음, 깊이 우선 탐색과 비트마스킹을 활용하면 문제를 풀 수 있습니다.

 

문제 해결하기

우선, N개의 마을을 0번 혹은 1번 선거구로 나눌 수 있는 모든 경우의 수를 만들어봅시다. 재귀함수를 사용할 수도 있지만 비트마스킹을 사용하면 손쉽게 모든 경우를 구할 수 있습니다. 1번 마을부터 N번 마을까지 하나의 비트 자릿수로 생각해봅시다. 우리는 N개의 마을을 0번 선거구와 1번 선거구로 만들 수 있으며, 이렇게 만든 비트열을 합쳐서 10진수로 바꿀 수 있습니다. 그리고 우리는 이렇게 나온 10진수를 반복문을 사용하여 간단하게 표현할 수 있습니다. 1번 마을부터 N번 마을을 편의상 0번 마을부터 (N-1)번 마을로 바꾼다면 훨씬 간단하게 찾을 수 있습니다. 바로, for( int k=0; k<(1<<N) ; k++ ) 를 사용하면 됩니다.

 

이렇게 모든 경우의 수를 찾았다면 이제는 각각의 경우가 선거구를 나누는 규칙에 위배되는지 확인하면 됩니다. 선거구를 나누기 위해서는 다음 2가지 규칙을 지켜야 합니다. 첫 번째, 같은 선거구 마을은 항상 연결되어 있어야 합니다. 두 번째, 0번 혹은 1번 선거구만 있어서는 안됩니다. 위의 규칙들을 준수했는지 확인하기 위해서는 DFS탐색을 활용할 수 있습니다. 한 번도 탐색하지 않은 마을을 2번 선정해서 같은 선거구의 인접한 마을로 탐색을 진행한 다음, 탐색의 결괏값을 확인하면 됩니다. 만약, 2번의 DFS 탐색을 끝난 후에도 아직 탐색하지 않은 마을이 있다면 규칙을 준수하지 않았음을 의미합니다. 혹은 0번 또는 1번 선거구만 있다면 역시나 규칙을 준수하지 않았음을 의미합니다. 하지만, 앞의 2가지 경우를 제외한 모든 경우에는 선거구를 올바르게 나누었다는 의미이며, 이 경우에는 두 선거구의 인구수의 차이를 구하면 됩니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define NMAX 15
#define INF 987654321
using namespace std;
 
int N, t, p;
int people[NMAX];
int maps[NMAX][NMAX];
 
int idx, ret;
int val[2], check[NMAX], visited[NMAX];
 
int abs(int k) { return k>0 ? k:-k; }
 
void dfs(int cur, int no) {
    for(int nxt=0;nxt<N;nxt++) {
        if(maps[cur][nxt] and check[cur] == check[nxt] and visited[nxt] == -1) {
            visited[nxt] = no;
            dfs(nxt, no);
        }
    }
}
 
bool isPossible() {
    int tmp[2]={0,0};
    
    for(int i=0;i<N;i++) {
        if(visited[i] == -1) return 0;
        tmp[visited[i]]++;
    }
    
    return !(tmp[0]==0 or tmp[1]==0);
    
}
 
int main() {
    // 입력
    scanf("%d", &N);
    for(int i=0;i<N;i++) scanf("%d", &people[i]);
    for(int i=0;i<N;i++) {
        scanf("%d", &t);
        for(int j=1;j<=t;j++) {
            scanf("%d", &p);
            maps[i][p-1] = 1;
        }
    }
    
    // 탐색
    ret = INF;
    for(int k=0;k<(1<<N);k++) {
        // 두 선거구로 나누기
        for(int j=0;j<N;j++) {
            if((k & (1<<j)) == 0) check[j] = 0;
            else check[j] = 1;
        }
        
        // 초기화
        idx = 0;
        memset(visited, -1, sizeof(visited));
        
        // 0번 선거구
        while(visited[idx] != -1) idx++;
        visited[idx] = 0;
        dfs(idx, 0);
        
        // 1번 선거구
        while(visited[idx] != -1) idx++;
        visited[idx] = 1;
        dfs(idx, 1);
        
        // 결과 확인
        if(isPossible()) {
            val[0] = val[1] = 0;
            for(int i=0;i<N;i++) val[check[i]] += people[i];
            
            ret = min( ret, abs(val[0] - val[1]) );
        }
    }
    
    // 출력
    if(ret == INF) printf("-1");
    else printf("%d", ret);
}
 

후기

2번의 DFS 탐색이 조금은 귀찮은 문제였습니다. 하지만, 비트마스킹을 활용하여 기본적인 브루트포스를 진행하는 방법을 소개해주는 기본적인 문제라고 생각합니다. 비트마스킹에 대해 궁금한