[알고리즘 문제] 백준17471 - 게리멘더링

www.acmicpc.net/problem/17471

17471번: 게리맨더링

문제는 아래의 흐름으로 풀 수 있습니다.

 

1. 선거구를 나눌 수 있는 모든 케이스로 나누어 줍니다.

next_permutation을 사용해도 되고 재귀를 사용해도 됩니다. 풀이에서는 재귀를 사용하였고 bool 1차원 배열을 사용하였습니다.

 

2. 케이스마다 각각의 선거구의 지역들이 모두 연결되었는지 검사합니다(연결 안되있으면 다음 케이스)

여기서 고민을 많이 했고, union-find방법을 사용할까 하다가, 다른분의 코드를 참고하여 bfs방식을 사용하였습니다.

 

3. 모두 연결되었다면 차이가 최소가 되는 인구수로 갱신해 줍니다.

각 선거구마다 인구수를 더해 그 차이값을 구하고 최소값인지 검사해줍니다.

 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 11;

int population[MAX] = {0};
int N;
int zoneDivide[MAX] = {0};
int ans = 987654321;
vector<int> matrix[MAX];

bool isConnect(vector<int> vec)
{
    int visited[MAX] = {0};
    queue<int> q;
    q.push(vec[0]);
    visited[vec[0]] = 1;

    while (!q.empty()) 
    {
        int cur = q.front();
        q.pop();

        for (int k = 0; k < matrix[cur].size(); k++)
        {
            int next = matrix[cur][k];

            if (find(vec.begin(), vec.end(), next) == vec.end() || visited[next])
            {
                continue;
            }

            q.push(next);
            visited[next] = 1;
        }
    }

    for (int k = 0; k < vec.size(); k++) // 
    {
        if (!visited[vec[k]])
        {
            return false;
        }
    }

    return true;
}

void divide(int index, int depth, int len)
{
    if (index > N)
    {
        return;
    }

    if (depth == len) // 선거구를 쪼갰다면, 각 선거구의 지역들이 모두 연결되었는지 검사하고, 인구차이를 갱신
    {
        vector<int> vec1;
        vector<int> vec2;

        for (int i = 0; i < N; i++) // zoneDivide[i]가 1인 부분과 0인 부분을 나눔
        {
            if (zoneDivide[i])
            {
                vec1.push_back(i);
            }
            else
            {
                vec2.push_back(i);
            }
        }
        if (isConnect(vec1) && isConnect(vec2)) // 두 선거구의 지역들이 모두 연결되어 있는지 검사
        {
            int result = 0;
            for (int i = 0; i < N; i++)
            {
                if (zoneDivide[i])
                {
                    result += population[i];
                }
                else
                {
                    result -= population[i];
                }
            }
            ans = min(ans, abs(result));
        }
        return;
    }

    zoneDivide[index] = 1;
    divide(index + 1, depth + 1, len);

    zoneDivide[index] = 0;
    divide(index + 1, depth, len);
}

int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> population[i];
    }

    for (int i = 0; i < N; i++)
    {
        int n;
        cin >> n;
        for (int j = 0; j < n; j++)
        {
            int nn;
            cin >> nn;
            matrix[i].push_back(nn - 1);
        }
    }

    for (int len = 1; len <= N - 1; len++)
    {
        divide(0, 0, len); // 각 선거구를 len, N-len크기 만큼 나눔, len 범위가 N-1인 이유는 무조건 두개의 선거구가 나와야 하기 때문
    }

    if (ans == 987654321)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ans << endl;
    }

    return 0;
}