백준 17471(게리맨더링) c++

문제

17471번: 게리맨더링

n개의 노드와 간선정보가 주어지면, 위와 같이 빨간색 부분과 파란색 부분을 나누어, 빨간색 부분의 합과 파란색 부분의 합의 최솟값을

구하는 문제입니다.

물론 각 노드마다 값은 주어집니다.

또한 같은 부분에 속하는 모든 노드는 서로 연결되어 있어야 합니다.

1) 일단 빨간색, 파란색 부분을 나누는 경우의 수, 즉 조합을 생각해야 합니다.

2) 부분을 나눴으면, 나눈 부분들이 실제로 가능한지 판별해야 합니다.

   2-1) 부분은 최소 1개의 노드를 가져야합니다.

   2-2) 부분에 속하는 노드들은 서로 이어져 있어야 합니다.

위의 작성한 순서대로 코드를 작성해 보았습니다.

 

1)

void dfs(int start, int cnt)
{
    if (cnt >= 1)
        if (check())
        {
            cal();
        }

    for (int i = start; i <= n; i++)
    { // 조합 부분
        if (team[i])
            continue;
        team[i] = true;
        dfs(i, cnt + 1);
        team[i] = false;
    }
}

start는 현재 내가 가리키고 있는 노드 번호이고, cnt는 현재 내가 팀으로 고른 인원 수 입니다.

따라서 처음 if문으로 들어가려면, cnt가 최소 1이상이어야 합니다.

 

2-1)

bool check()
{
    vector<int> A, B;
    for (int i = 1; i <= n; i++)
    { // 팀에 따라 각각 A, B에 넣어주기
        if (team[i])
            A.push_back(i);
        else
            B.push_back(i);
    }
    if (A.size() == 0 || B.size() == 0)
        return false; // 0명 뽑은 경우

    if (!connection(A, true))
        return false;
    if (!connection(B, false))
        return false;
    return true;
}

A부분, B부분으로 나누어 벡터에 넣어줍니다.

각각의 벡터의 사이즈가 0이면 부분에 노드가 0개이므로 탈락입니다.

 

2-2)

bool connection(vector<int> V, bool b)
{ // 각 팀의 노드들이 연결되어 있는지
    memset(Visit, false, sizeof(Visit));
    queue<int> q;
    q.push(V[0]);
    Visit[V[0]] = true;
    int cnt = 1;
    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        for (auto nxt : v[node])
        {
            if (team[nxt] == b && !Visit[nxt])
            {
                Visit[nxt] = true;
                cnt++;
                q.push(nxt);
            }
        }
    }
    return V.size() == cnt;
}

bfs를 이용해 각 벡터에 넣어진 노드들이 서로 이어져 있는지 확인합니다.

void cal()
{
    int a = 0, b = 0;
    int d;
    for (int i = 1; i <= n; i++)
    {
        if (team[i])
            a += arr[i];
        else
            b += arr[i];
    }
    d = abs(a - b);
    ans = min(ans, d);
}

저 위에 모든 조건을 만족하면 이제 각 노드끼리의 차이의 최솟값을 계산해주어야 합니다.

---

전체 코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#define INF 2000000000
using namespace std;
using ll = long long;
int arr[11];
vector<int> v[11];
bool team[11];
int n;
int ans = INF;
void dfs(int start, int cnt);
bool check();
bool connection(vector<int> V, bool b);
void cal();
bool Visit[11];
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];

    for (int i = 1; i <= n; i++)
    {
        int a;
        cin >> a;
        for (int j = 0; j < a; j++)
        {
            int b;
            cin >> b;
            v[i].push_back(b);
        }
    }

    dfs(1, 0);
    if (ans == INF)
        cout << -1;
    else
        cout << ans;

    return 0;
}
void dfs(int start, int cnt)
{
    if (cnt >= 1)
        if (check())
        {
            cal();
        }

    for (int i = start; i <= n; i++)
    { // 조합 부분
        if (team[i])
            continue;
        team[i] = true;
        dfs(i, cnt + 1);
        team[i] = false;
    }
}
bool check()
{
    vector<int> A, B;
    for (int i = 1; i <= n; i++)
    { // 팀에 따라 각각 A, B에 넣어주기
        if (team[i])
            A.push_back(i);
        else
            B.push_back(i);
    }
    if (A.size() == 0 || B.size() == 0)
        return false; // 0명 뽑은 경우

    if (!connection(A, true))
        return false;
    if (!connection(B, false))
        return false;
    return true;
}
bool connection(vector<int> V, bool b)
{ // 각 팀의 노드들이 연결되어 있는지
    memset(Visit, false, sizeof(Visit));
    queue<int> q;
    q.push(V[0]);
    Visit[V[0]] = true;
    int cnt = 1;
    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        for (auto nxt : v[node])
        {
            if (team[nxt] == b && !Visit[nxt])
            {
                Visit[nxt] = true;
                cnt++;
                q.push(nxt);
            }
        }
    }
    return V.size() == cnt;
}
void cal()
{
    int a = 0, b = 0;
    int d;
    for (int i = 1; i <= n; i++)
    {
        if (team[i])
            a += arr[i];
        else
            b += arr[i];
    }
    d = abs(a - b);
    ans = min(ans, d);
}