문제

17471번: 게리맨더링

풀이

N의 크기가 최대 10인데도 불구하고 추가시간 없는 0.5초에 쫄아서 완전탐색을 생각하지 못했다.

1 ~ n 까지의 구역을 두 개로 나누기 위해 비트마스킹을 이용해서 완전탐색을 했다.
두 선거구를 나누었을 때 각 선거구의 구역은 서로 이어져 있어야 하므로 그래프 탐색을 했을 때 전부 탐색이 가능해야 한다.
두 선거구를 비트마스킹으로 표시하는 uint32 크기의 red 변수와 각 그래프 탐색 후 방문 여부를 저장하는 visited 를 비교하여 같은 선거구의 각 구역이 연결되어 있는지 확인하였다.

두 선거구 그룹을 서로 그래프 탐색하여 모두 연결되어 있는지 확인하고 연결되어 있다면 그래프 탐색할때 구한 각 선거구의 인구를 비교하여 그 차가 최소가 되는 값을 저장한다.

문제를 풀때 두 선거구를 red 와 blue로 하고 문제를 풀었는데, red에 속한 위치를 비트1로 표현하는 변수 red가 있을 때 이와 반대되는 비트를 가지는 blue를 구하기 위해서는 ~( (~0 << n) ^ red)로 구할 수 있었다.

코드

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> population;
vector<vector<int>> graph;
unsigned int red = 0;
unsigned int visited = 1;
int answer = INT32_MAX;

int sumVec(vector<int>& input)
{
    int ret = 0;
    for (auto i: input)
        ret += i;
    return ret;
}

int min(int a, int b) { return a < b ? a : b; }
int abs(int a) { return a < 0 ? -a : a; }

int findBlue(int v)
{
    int ret = population[v];
    for (int next : graph[v])
    {
        if (red & 1 << next)
            continue;
        if (visited & 1 << next)
            continue;

        visited = visited | 1 << next;
        ret += findBlue(next);
    }
    return ret;
}

int findRed(int v)
{
    int ret = population[v];
    for (int next : graph[v])
    {
        if (!(red & 1 << next))
            continue;
        if (visited & 1 << next)
            continue;

        visited = visited | 1 << next;
        ret += findRed(next);
    }
    return ret;
}

int main() 
{
    cin >> n;
    population.resize(n); 
    graph.resize(n);

    for (int i=0; i<n; ++i)
        cin >> population[i];
    
    for (int i=0; i<n; ++i)
    {
        int cnt;
        cin >> cnt;
        while (cnt--)
        {
            int dest;
            cin >> dest;
            graph[i].push_back(dest-1);
        }
    }

    int totalPo = sumVec(population);

    while (red != 1 << n)
    {
        ++red;
        int redPopulation;
        int bluePopulation;

        // 파란색 시작점 찾기
        int blueStart;
        for (int i=0; i<n; ++i)
        {
            if (red & 1 << i)
                continue;
            blueStart = i;
            break;
        }
        // 파란색 탐색
        visited = 0 | 1 << blueStart;
        bluePopulation = findBlue(blueStart);
        if (visited != ~( (~0 << n) ^ red))
            continue;

        // 빨간색 시작점은 항상 1, 빨간색 탐색
        visited = 1;
        redPopulation = findRed(0);
        
        if (visited != red)
            continue;
        
        answer = min(answer, abs(bluePopulation - redPopulation));
        
    }

    if (answer == INT32_MAX)
        answer = -1;
    cout << answer << endl;
    return 0;
}

두 선거구는 구별하지 않기 때문에 두 선거구를 빨간색과 파란색으로 나눈다고 가정하게 되면 1번 지역을 항상 빨간색에 넣어둔다 가정해도 문제되지 않는다. 이 사실을 이용해서 더 빠른 코드를 작성할 수 있지 않을까 생각도 해보았다. $2^n$ 아 아닌 $2^{n-1}$까지 반복하면 되기 때문에