게리맨더링 (feat. 백준, 17471번)

게리맨더링
https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <set>
#include <queue>
using namespace std;
int N, ans, people[11];
bool check[11]; // check은 지역구1에 대한 마킹
set<int> arr[11];
bool bfs(){
    queue<int> q1, q2;
    bool visit1[11]{false}, visit2[11]{false}, check1[11]{false}, check2[11]{false};
    for(register int i = 1; i <= N; ++i)
        if(check[i])
            check1[i] = true;
        else
            check2[i] = true;
    for(register int i = 1; i <= N; ++i)
	    if(check1[i]){
			q1.push(i);
			visit1[i] = true;
			break;
		}
    for(register int i = 1; i <= N; ++i)
	    if(check2[i]){
			q2.push(i);
			visit2[i] = true;
			break;
		}
    // 조합으로 선택된 지역구1은 모두 이어져있는가?
    while(!q1.empty()){
        auto p = q1.front(); q1.pop();
        for(auto iter = arr[p].begin(); iter != arr[p].end(); ++iter)
            if(!visit1[*iter] && !check2[*iter])
                visit1[*iter] = true, q1.push(*iter);
    }
    for(register int i = 1; i <= N; ++i)
        if(check1[i] && !visit1[i])
            return false;
    // 조합으로 선택된 지역구2는 모두 이어져있는가?
    while(!q2.empty()){
        auto p = q2.front(); q2.pop();
        for(auto iter = arr[p].begin(); iter != arr[p].end(); ++iter)
            if(!visit2[*iter] && !check1[*iter])
                visit2[*iter] = true, q2.push(*iter);
    }
    for(register int i = 1; i <= N; ++i)
        if(check2[i] && !visit2[i])
            return false;
    return true;
}
void dfs(register int idx, register int cnt){
    if(cnt > 0){
        if(bfs()){
            register int t1 = 0, t2 = 0;
            for(register int i = 1; i <= N; ++i){
                if(check[i])
                    t1 += people[i];
                else
                    t2 += people[i];
            }
            ans = min(ans, abs(t1 - t2));
        }
    }
    if(cnt == N / 2){
        return;
    }
    for(register int i = idx; i <= N; ++i)
        if(!check[i]){
            check[i] = true;
            dfs(i, cnt + 1);
            check[i] = false;
        }
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N;
    for(register int n = 1; n <= N; ++n)
        cin >> people[n];
    for(register int n = 1, cnt, v; n <= N; ++n){
        cin >> cnt;
        for(register int i = 0; i < cnt; ++i){
            cin >> v;
            arr[n].insert(v), arr[v].insert(n);
        }
    }
    memset(check, false, sizeof(check));
    ans = 99999999;
    dfs(1, 0);
    if(ans == 99999999)
        cout << -1;
    else
        cout << ans;
	return 0;
}
// *&)*@*

 

반응형

1. 골드 5임에도 상당히 어렵게 느껴졌습니다만 정리를 끝내니 그렇게 어렵진 않습니다.
2. 지역구1과 2의 각각 조합을 구해줍니다.
3. 조합이 연결되는지를 확인합니다. 이때 지역구1의 연결을 확인한다면 그 값이 지역구2에 존재해서는 안됩니다. (이 부분으로 2% 틀림 판정을 계속 받았습니다.)
4. 이후 지역구1과 지역구2가 연결되어 있다는 것이 확인된다면 두 값의 차이를 구해줍니다. (지역구1에 1,2가 있고 1,2가 직접적으로 연결되지 않았더라도 1->4->2 와 같이 연결이 가능합니다. 단 4는 지역구2에 있으므로 이와 같은 경우는 이어지지 않는다고 봐야합니다.)