백준 17471. 게리맨더링

17471. 게리맨더링

• 역량테스트에 나왔던 문제라고 해서 풀어보았다.
• 단순 알고리즘 적용보단 알고리즘 적용한 결과를 가지고 또다시 알고리즘을 적용하거나 시뮬레이션을 돌리는 형태로 문제가 많이 나오는 것 같다.

풀이 과정

1. 선거구를 2개로 나눈다. N개의 구역이 있다면 N/2까지 나눠봐야 한다. 즉 N=6이면 (1,5), (2,4), (3,3)으로 나누면 된다. 지역을 나누는 것은 조합 짜듯 구현하였다. (go함수)
2. 지역을 나누고 나선 나눈걸 각각 firstRegion, secondRegion에 넣어준다. 넣어준 것을 가지고 각 선거구 안에 있는 지역의 번호를 가지고 BFS를 돌려서 모두 연결이 되어있는지 확인하였다. (isConnected함수)
3. firstRegion, secondRegion 모두 연결이 되어있다면 두 선거구에 포함된 인구의 차이를 구하고 ans와 비교하여 최솟값으로 갱신한다. 여기서 주의할 것은 1개는 무조건 연결이 되어있는 상태라는 점 정도일 것 같다.

소스 코드

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

using namespace std;

int map[11][11];
int people[11];
int visit[11];
int n;
vector<int> firstRegion;
vector<int> secondRegion;
int ans = 987654321;

// v에 있는 값들의 위치를 모두 이으면 연결 되는지 확인
bool isConnected(vector<int>& v)
{
    int check[11];
    fill(check, check + 11, 0);
    for (int i = 0; i < v.size(); i++)
    {
        check[v[i]] = 1;
    }

    // 1개는 무조건 연결
    if (v.size() == 1)
    {
        return true;
    }

    queue<int> q;
    q.push(v[0]);
    while (!q.empty())
    {
        int i = q.front();
        q.pop();
        for (int j = 1; j <= n; j++)
        {
            // 연결 되어 있는지 확인
            // 연결 되어 있다면 큐에 넣고 check[j]=0으로 바꿈
            if (map[i][j] == 1 && check[j] == 1)
            {
                q.push(j);
                check[j] = 0;
            }
        }
    }

    // v에 있는 정점들이 서로 연결 되어있는지 확인 -> check배열이 모두 0인지
    bool flag = true;
    for (int i = 1; i <= n; i++)
    {
        if (check[i] == 1)
        {
            flag = false;
            break;
        }
    }
    return flag;
}

// 두가지로 나누는 함수
void go(int cnt, int m, int start)
{
    if (cnt == m)
    {
        // 두 가지로 나눠서 저장
        for (int i = 1; i <= n; i++)
        {
            if (!visit[i])
            {
                firstRegion.push_back(i);
            }
            else
            {
                secondRegion.push_back(i);
            }
        }

        // 두개 모두 연결되었다면
        if (isConnected(firstRegion) && isConnected(secondRegion))
        {
            int sum1 = 0;
            int sum2 = 0;
            for (int i = 0; i < firstRegion.size(); i++)
            {
                sum1 += people[firstRegion[i]];
            }
            for (int i = 0; i < secondRegion.size(); i++)
            {
                sum2 += people[secondRegion[i]];
            }
            ans = min(ans, abs(sum1 - sum2));
        }
        // 나웠던 벡터 비워줌
        firstRegion.clear();
        secondRegion.clear();
        return;
    }

    for (int i = start; i <= n; i++)
    {
        if (!visit[i])
        {
            visit[i] = 1;
            go(cnt + 1, m, i + 1);
            visit[i] = 0;
        }
    }
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> people[i];
    }
    for (int i = 1; i <= n; i++)
    {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++)
        {
            int x;
            cin >> x;
            map[i][x] = 1;
            map[x][i] = 1;
        }
    }

    for (int i = 1; i <= n / 2; i++)
    {
        for (int i = 1; i <= 10; i++)
        {
            visit[i] = 0;
        }
        go(0, i, 1);
    }

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

코드도 많이 복잡하고 N=6이면 (123, 456)과 (456, 123)의 결과가 같아서 한 번만 해도 되지만 위 코드는 두 개 모두 실행해보기 때문에 시간이 좀 더 걸린다. 이점은 개선이 필요할 것 같다.

전체 소스 코드