백준 17471번: 게리맨더링

1. 문제 분석

문제의 조건들은 다음과 같다:

  1. N개의 구역들을 두 개의 선거구로 나눈다
  2. 각 선거구에는 최소 1개의 구역이 포함되어야 한다
  3. 같은 선거구에 포함된 구역들은 서로 연결되어야 한다 (사이에 다른 선거구에 포함된 구역이 있어서는 안 된다)
  4. 각 선거구의 총 인구 수의 차의 최솟값을 구해야 한다

주의할 점은 한 구역에 인접한 구역이 한 개도 없을 수도 있다는 것이다.

  각 구역마다 인접한 구역이 있는 점, 한 선거구 내에 속한 구역들이 모두 연결되어야 한다는 조건이 있는 점 등을 미루어 보아 그래프 알고리즘을 통해 풀 수 있는 문제라고 생각하였다. 그런데, 각 선거구로 어떻게 나눌지 처음에 조금 헤매었다. articulation point를 찾아야 하나라는 생각도 했지만 코드가 너무 복잡해질 것 같아서 그렇게 하지 않고 N의 최댓값이 10밖에 되지 않아서 그냥 간단하게 모든 경우의 수를 구해보기로 하였다.
  우선, 재귀함수를 이용해서 N개의 구역들을 두 개의 선거구로 나누는 경우의 수를 구하고, 각 경우의 수를 찾을 때 마다 그에 따른 처리를 해주었다. 우선 각 선거구의 총 인구수를 구하고, 집합을 2개 만들어서 각 선거구에 포함된 구역들을 넣어주었다. 그리고 이를 이용하여 집합 중 하나가 비어있으면 조건 2에 어긋나므로 처리를 끝냈다.
  그 다음에는 조건 3을 확인하기 위해 dfs 방식을 이용하였다. 선거구에 포함된 구역들 중 하나에서 시작해서 인접한 구역들 중 같은 선거구에 포함된 구역이 있으면 이 구역을 앞서 만든 집합에서 제거하고 다음 계산을 위해 스택에 쌓아주었는데, 이 스택이 비거나 해당 선거구의 집합이 빌 때 까지 while문을 사용하여 같은 작업을 반복하였다. 만약 스택이 비어서 루프에서 빠져나왔는데 집합이 비어있지 않다면 이 선거구의 구역들은 서로 연결되어 있지 않은 것이다. 두 선거구에 대해 똑같은 처리를 해주고, 둘 다 조건 3을 만족했을 시에만 총 인구수의 차를 구해서 최솟값을 갱신해준다.

2. 코드

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int N;                 //구역 수
int population[11];    //구역 별 인구 수
bool division[11];     //선거구 구분
vector<int> adj[11];   //구역 별 인접 구역
int min_diff=-1;       //최소 인구 차


/**
 * 구역 s가 포함된 선거구 sector 내의 모든 구역이 서로 연결되어 있는지 확인한다
 * @param s       시작 구역
 * @param sector  같은 선거구에 포함된 구역들
 * @return        모든 구역이 서로 연결되어 있으면 true, 아니면 false
 */
bool dfs(int s, set<int> sector){
    vector<int> nodes;  //지나간 구역 저장

    //s 구역에서 탐색 시작
    nodes.push_back(s);
    sector.erase(s);

    while(!nodes.empty() && !sector.empty()){
        int v = nodes.back(); nodes.pop_back();
        //현재 구역에서 인접한 구역들 중, sector 집합에 포함된 구역들을 찾음
        for(auto x:adj[v]){
            if(sector.count(x)) {
                //벡터에 새로운 연결된 구역 저장
                nodes.push_back(x);
                //지나간 구역 집합에서 삭제
                sector.erase(x);
            }
        }
    }
    return sector.empty();
}


/**
 * n개의 구역들을 2개의 선거구로 나누는 순열 생성하고 그 때의 경우의 수에 대해 인구 수 차를 구함
 * @param n  구역 개수
 */
void perm(int n){
    //모든 구역에 대한 처리가 끝남
    if(n==N+1){
        int sum_a = 0; int sum_b = 0;    //각 선거구 총 인구 수
        int sa, sb;                      //탐색을 시작할 구역
        set<int> sec_a; set<int> sec_b;  //각 선거구에 포함된 구역

        for(int i=1; i<=N; i++){
            //선거구 A에 포함된 경우
            if(division[i]) {
                sum_a += population[i];
                sec_a.insert(i);
                sa = i;
            }
            //선거구 B에 포함된 경우
            else {
                sum_b += population[i];
                sec_b.insert(i);
                sb = i;
            }
        }

        //각 선거구에 구역이 최소 1개 포함되어 있는 지 확인
        if(sec_a.empty() || sec_b.empty())
            return;

        //각 선거구의 구역들이 전부 연결되어 있는 지 확인
        if(dfs(sa, sec_a) && dfs(sb, sec_b)){
            //최소 인구 수 구함
            int diff = abs(sum_a-sum_b);
            if(min_diff==-1 || min_diff>diff)
                min_diff = diff;
        }
    }
    else{
        //구역 n을 선거구 A에 포함하는 경우
        division[n] = true;
        perm(n+1);
        //구역 n을 선거구 B에 포함하는 경우
        division[n] = false;
        perm(n+1);
    }
}


/**
 * main 함수
 */
int main(){
    int v, n;
    ios_base::sync_with_stdio(false); cin.tie(0);

    //입력
    cin>>N;
    for(int i=1; i<=N; i++)
        cin>>population[i];
    for(int i=1; i<=N; i++){
        cin>>n;
        for(int j=0; j<n; j++){
            cin>>v;
            adj[i].push_back(v);
        }
    }

    //문제 해결
    perm(1);

    //결과 출력
    cout<<min_diff;
}