백준[17471] 게리맨더링

본 문제는 아래의 출처에서 확인할 수 있다.

 

https://www.acmicpc.net/problem/17471

 

인증된 문제집에서 '삼성 A형 기출'에 있는 문제이다. 

 

DFS를 활용하여 문제를 해결할 수 있다. 필자는 2그룹으로 나누는 방법으로 부분집합을 사용하였으며, 그룹을 나눈 후, 문제의 조건에 맞게 DFS를 수행하였다. 

 

다른사람은 조합, Union-find 등을 사용하였으며, 필자는 부분 집합으로 그룹으로 나누었다. N의 크기가 작기 때문에 부분집합으로 중복된 그룹을 또 탐색하지만, 시간초과에 걸릴 것 같지는 않았다. 

부분집합으로 하게되면 (1,2,3) (4,5,6) 이란 그룹을 (4,5,6) (1,2,3) 으로 또 탐색을 하게된다.

 

그룹화 이후, DFS를 통해 각 그룹에 맞게 탐색이 가능한지 확인을 하며 이미 방문된 노드라면 그 그룹에 속해있기 때문에 전체 노드를 탐색할 필요는 없다. 같은 그룹에 있는 노드끼리는 연결되어야 함으로 이 부분을 잘 체크하여 문제를 해결할 수 있다.

 

*주석파트는 문제를 풀면서 디버깅과 현재사항을 체크하기 위한것이다.*

 

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iterator>
#include<deque>
#include<sstream>
 
using namespace std;
 
int n, visit[11], num[11] = { 0 }, visit2[11] = { 0 }, arr2[11] = { 0 },chk,chk2,ans=987654321,chk3,chk4;
int check;
vector<int> arr[11];
 
void dfs(int a, int b) {
    //cout << a << " ";
    if (b == 0) chk3++;
    else if (b == 1) chk4++;
    for (int i = 0; i < arr[a].size(); i++) {
        if (visit[arr[a][i]] == 0 && visit2[arr[a][i]] == b) {
            visit[arr[a][i]] = 1;
            dfs(arr[a][i], b);
        }
    }
}
 
void p(int a) {
    if (a == n+1) {
        for (int i = 1; i <= n; i++) {
            if (visit2[i] == 1) {
                //printf("%d ", arr2[i]);
                chk2++;
            }
            else if (visit2[i] == 0) chk++;
            //printf("%d ", visit2[i]);
        }
        //printf("visit[5] = %d\n",visit[5]);
        //cout <<"원래 각 갯수들" <<  chk << "  " << chk2 << endl;
        for (int i = 1; i <= n; i++) {
            //printf("\n");
            if (visit[i] == 1) continue;
            visit[i] = 1;
            //if (visit2[5] == 0) chk++;
            //else if (visit[5] == 1) chk2++;
            dfs(i, visit2[i]);
            if (visit2[i] == 0 && chk3 != chk) {
                check = 1;
                break;
            }
            if (visit2[i] == 1 && chk2 != chk4) {
                check = 1;
                break;
            }
        }
        //cout << chk << "  " << chk2 << "  " << chk3 << "  " << chk4 << endl;
        //printf("한가지 부분집합 끄");
        if (check != 1 && chk == chk3 && chk2 == chk4) {
            int sum = 0, sum2 = 0;
            for (int i = 1; i <= n; i++) {
                
                if (visit2[i] == 1) sum += num[i];
                else if (visit2[i] == 0) sum2 += num[i];
            }
            //printf("\n\n");
            ans = min(ans,abs(sum - sum2));
        }
        memset(visit, 0, sizeof(visit));
        chk3 = chk4 = 0;
        chk = chk2 = check = 0;
        return;
    }
    visit2[a] = 1;
    p(a+1);
    visit2[a] = 0;
    p(a + 1);
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &num[i]);
    for (int i = 1; i <= n; i++) {
        int t;
        scanf("%d", &t);
        for (int j = 0; j < t; j++) {
            int a;
            scanf("%d", &a);
            arr[i].push_back(a);
            //arr[a].push_back(i);
            
        }
    }
    for (int i = 1; i <= n; i++) arr2[i] = i;
    p(1);
    //for (int i = 1; i <= n; i++) {
        //cout << i << " : ";
        //for (int j = 0; j < arr[i].size(); j++) {
            //cout << arr[i][j] << " ";
        //}
        //printf("\n");
    //}
    if(ans != 987654321) cout << ans;
    else cout << -1;
    return 0;
}