게리맨더링 17471

문제

접근 방법

구역을 나누고 탐색하여 몇 개의 구역으로 나뉘는지 확인하는 문제이다. 2개의 구역인 경우 2개의 구역 차이의 최솟값을 확인하는 것을 목표로 한다.
N이 10 이하라는 점은 모든 경우를 확인해봐도 된다는 것이다.
또한 10 이하이기에 비트 마스크를 활용할 수도 있다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
vector<int> popul;
queue<int> q;
vector<vector<int>> map;
int N, ret = 1001, total = 0;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    popul = vector<int>(N);
    map = vector<vector<int>>(N, vector<int>());

    for (int i = 0; i < N; ++i)
    {
        cin >> popul[i];
        total += popul[i];
    }
    for (int i = 0; i < N; ++i)
    {
        int near;
        cin >> near;
        while (near--)
        {
            int nearNum;
            cin >> nearNum;
            --nearNum;
            map[i].push_back(nearNum);
        }
    }
    for (int i = 1; i < (1 << N); ++i)
    {
        int part = 0, visted = 0, my = 0;
        for (int j = 0; j < N; ++j)
        {
            if (visted & (1 << j)) // 이미 방문한 경우
                continue;
            visted = (visted | (1 << j));
            ++part;
            if (part > 2) // 구역이 2개 이상인 경우 넘어간다
            {
                q = queue<int>();
                break;
            }
            bool isSelected = (i & (1 << j)); // 누구의 선거구인지 확인
            if (isSelected)
                my += popul[j];
            q.push(j);
            while (!q.empty())
            {
                int cur = q.front();
                q.pop();
                for (int k : map[cur])
                {
                    if ((visted & (1 << k)) || (isSelected != bool(i & (1 << k)))) // 방문했거나 나와 다른 경우 넘어간다
                        continue;
                    visted = (visted | (1 << k)); // 방문 표시
                    if (isSelected)               // 내 선거구면 횟수를 더 해준다.
                        my += popul[k];
                    q.push(k);
                }
            }
        }
        if (part != 2)
            continue;
        int gap = total - (my << 1); // 상대 선거구 - 내 선거구 => 전체 선거구 - 내 선거구 *2
        if (gap < 0)
            gap *= -1;
        ret = ret > gap ? gap : ret;
    }
    if (ret == 1001)
        cout << -1;
    else
        cout << ret;
}

풀이

비트 마스크를 활용하여 풀었다. 무엇을 선택했는지와 무엇을 방문했는지를 비트 마스크로 표시하였고 구역이 2개를 넘어가는 경우 값을 무시하였다.
전체 선거구에서 내 선거구를 2배 해서 빼면 격차가 나온다는 점 또한 활용했다.
비트 마스크를 쓰며 실수했던 점이 있었는데 &연산하면 bool형으로 나오는 것이 아닌 int형으로 나오기에 비교 연산을 하면 int값과 bool의 비교여서 잘못된 값이 나오게 된다. bool로 캐스팅해서 사용해주어야 함을 알게 됐다.