[백준 17471] 게리맨더링 C++

www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

이 문제는 브루트포스 문제로, 모든 경우의 수를 다 시뮬레이션 돌려보고, 문제의 조건에 맞다면 경우의 수를 +1 해줍니다.

 

브루트포스 문제라고 생각했던 이유는 바로, N의 제한이 10밖에 안됐기 때문입니다. 

조합을 구하는데 시간복잡도는 약 O(2^N)으로, 2의 10승은 1024이고, 노드가 1개 이상일 때부터 조건이 가능하니까 때문에 2^10승 * 10정도로 생각했습니다.

 

 

원리는 두 개의 집단으로 나누면 되는데, DFS 조합을 구함으로써, 

하나의 집단을 만들어 놓고, 나머지 집단은 선택되지 않은 집단으로 나눔으로써 문제를 풀었습니다.

 

즉, DFS 조합으로 각 노드에 check표시를 해서, check표시가 된 구역은 1구역,

안된 구역은 2구역으로 나눈 뒤, 시뮬레이션을 돌려봄으로써, 문제에서 같은 구역끼리 요구하는 연결이 되어있고, 1개 이상의 노드가 있는지에 대해 검사하면 됩니다.

 

연결되어있다는 것을 판별하는 방법은, 노드 탐색하는 방식으로 각 노드를 저장한다음에, dfs로 노드를 따라가는 형식으로, 

따라 갈때마다 각 노드에 cnt++을 하여, 노드 개수랑 cnt값이 같은지 확인하면, 구역으로 나누어진 노드가 연결되어있는지 확인할 수 있습니다.

 

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

using namespace std;

const int MAX = 11;

int people[MAX];
vector<int>node[MAX];
bool selected[MAX];
bool visit[MAX];

int n;

int ans = __INT_MAX__;


bool isConnected(vector<int> &v, bool flag){
    memset(visit, false, sizeof(visit));
    queue<int> q;
    visit[v[0]] = true;
    q.push(v[0]);
    int cnt = 1;

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

        for (auto value: node[x]){ // 노드안에있는 값 다 꺼내서 탐색할 곳 큐에 넣어주기

            if (selected[value] != flag || visit[value]) continue;
            cnt++;
            visit[value] = true;	// 이미 갔던 노드는 못가도록 check표시
            q.push(value);
        }
    }

    if (v.size() == cnt) return true; // 탐색한 노드 개수랑, 구역의 노드 개수가 같다면 모두다 연결되어있다는 의미
    else return false;
}

bool isOk(){
    vector<int> a;
    vector<int> b;
    
    for (int i = 1; i <= n; i++){
        if (selected[i]) a.push_back(i);
        else b.push_back(i);
    }

    if (a.empty() || b.empty()) return false; // 둘 중 하나라도 비어있다면, 노드의 개수가 0이라는 의미

    if (!isConnected(a, true)) return false; // check표시한 구역이 연결되어있는지 검사 flag = true
    	
    if (!isConnected(b, false)) return false; // check표시가 안되어있는 구역이 연결되어있는지 검사 flag = false

    return true;


}
void calcu(){
    int a_sum = 0;
    int b_sum = 0;

    for (int i = 1; i <= n; i++){
        if (selected[i]) a_sum += people[i]; // 선택된 구역
        else b_sum += people[i]; 			// 선택이 안된 구역으로 나누어준다.
    }

    ans = min(ans, abs(a_sum - b_sum));


}

void dfs(int start, int depth){

    if (depth >= 1){ // 1개 이상이어도 시뮬레이션을 돌려본다. 
        if (isOk()){
            calcu();
        }
    }
    

    for (int i = start; i <= n; i++){
        if (selected[i]) continue;
        selected[i] = true;
        dfs(i + 1, depth + 1);
        selected[i] = false;
    }
}

void solution(){
    cin >> n;

    for (int i = 1; i <= n; i++){
        cin >> people[i];
    }
    for (int i = 1; i <= n; i++){
        int cnt;
        cin >> cnt;
        for (int j = 0; j < cnt; j++){
            int tmp;
            cin >> tmp;
            node[i].push_back(tmp); // 노드 양방향으로 연결시켜주기
            node[tmp].push_back(i); // 노드 양방향으로 연결시켜주기
        }
    }

    dfs(1, 0); // DFS 조합 만들기




    if (ans == __INT_MAX__) cout << -1 << '\n';
    else cout << ans << '\n';
}
int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();

    return 0;
}