[Problem Solving] BOJ 17471: 게리멘더링

문제 링크: https://www.acmicpc.net/problem/17471

 

그래프에서 지역구를 두 개로 나눈다. 한 지역구에는 적어도 하나의 노드를 가져야 하고, 한 지역구의 노드들을 하나의 연결요소여야 한다.

 

일단 모든 노드를 방문하는 bfs를 수행하는 데, bfs 호출 횟수가 3번 이상이라면, 그래프가 3개 이상으로 쪼개져있어서 두 개의 지역구로 나누는 것이 불가능 하다. 이 때는 -1을 출력하고 프로그램을 종료한다.

 

bfs 호출 횟수가 정확히 2번이라면, 쪼개진 두 개의 그래프의 노드의 인구의 합의 차이가 답이 된다.

 

bfs 호출 횟수가 정확히 한 번이라면, 전체 노드를 두 쪽을 내는 모든 경우의 수를 따져야한다.

노드 집합을 분리해서 하나는 v1에 다른 하나는 v2에 저장한다.

v1의 노드들이 하나의 연결 요소를 이루고, v2의 노드들이 하나의 연결 요소를 이룬다면, 각각의 인구의 합의 차이를 구해서 result에 최솟값을 갱신한다.

 

결과적으로 result를 출력하면 된다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
#define endl '\n'
using namespace std;

int N;
vector<int> populations;
vector<int> graph[11];
vector<bool> visited;
int cnt = 0;
int result = 987654321;

void input()
{
    cin >> N;
    populations.resize(N + 1);
    for (int i = 1; i <= N; i++)
    {
        cin >> populations[i];
    }
    for (int i = 1; i <= N; i++)
    {
        int numOfNeighbor;
        cin >> numOfNeighbor;
        for (int j = 0; j < numOfNeighbor; j++)
        {
            int neighbor;
            cin >> neighbor;
            graph[i].push_back(neighbor);
        }
    }
}

void bfs(int s)
{
    queue<int> q;

    visited[s] = true;
    q.push(s);
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (auto next : graph[cur])
        {
            if (!visited[next])
            {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

int cnt_bfs(int s)
{
    int ret = 0;
    queue<int> q;

    visited[s] = true;
    q.push(s);
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        ret += populations[cur];
        for (auto next : graph[cur])
        {
            if (!visited[next])
            {
                visited[next] = true;
                q.push(next);
            }
        }
    }
    return ret;
}

bool component_bfs(vector<int> v)
{
    visited.assign(N + 1, true);

    for (int i : v)
    {
        visited[i] = false;
    }

    queue<int> q;
    visited[v[0]] = true;
    q.push(v[0]);
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        for (auto next : graph[cur])
        {
            if (!visited[next])
            {
                visited[next] = true;
                q.push(next);
            }
        }
    }

    for (int i : v)
    {
        if (visited[i] == false)
        {
            return false;
        }
    }
    return true;
}

void solution()
{
    visited.resize(N + 1, false);
    for (int i = 1; i <= N; i++)
    {
        if (!visited[i])
        {
            ++cnt;
            bfs(i);
            if (cnt >= 3)
            {
                cout << -1 << endl;
                exit(0);
            }
        }
    }

    if (cnt == 2)
    {
        visited.assign(N + 1, false);
        vector<int> operand;
        for (int i = 1; i <= N; i++)
        {
            if (!visited[i])
            {
                operand.push_back(cnt_bfs(i));
            }
        }
        result = abs(operand[0] - operand[1]);
    }

    else
    {
        vector<int> arr;
        for (int i = 1; i <= N; i++)
        {
            arr.push_back(i);
        }
        for (int i = 1; i <= (N / 2); i++)
        {
            vector<bool> mask(arr.size(), false);
            fill(mask.begin(), mask.begin() + i, true);
            do
            {
                vector<int> v1;
                vector<int> v2;
                for (int j = 0; j < arr.size(); j++)
                {
                    if (mask[j])
                        v1.push_back(arr[j]);
                    else
                        v2.push_back(arr[j]);
                }
                if (component_bfs(v1) && component_bfs(v2))
                {
                    int s1 = 0;
                    int s2 = 0;
                    for (int k : v1)
                    {
                        s1 += populations[k];
                    }
                    for (int k : v2)
                    {
                        s2 += populations[k];
                    }
                    result = min(result, abs(s1 - s2));
                }
            } while (prev_permutation(mask.begin(), mask.end()));
        }
    }
}

void output()
{
    cout << result << endl;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solution();
    output();

    return 0;
}