[BOJ 17417] 게리맨더링 (C++)

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

17471번: 게리맨더링

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;

int N;
int populations[11];
vector<vector<int> > adj(11);
int ans = INT_MAX;
bool visit[11];
vector<int> A; 
vector<int> B;

int calc(vector<int>& v){
    int sum=0;
    for (int i=0; i<v.size(); i++){
        sum+=populations[v[i]];
    }
    return sum;
}

void dfs(int AorB, int id, vector<bool> &v){
    visit[id]=true;
    for (int i=0; i<adj[id].size(); i++){
        int neighbor=adj[id][i];
        if ((AorB==0 && v[neighbor-1]) || (AorB==1 && !v[neighbor-1])){   //각자 그룹인 애들만 탐색 가능
            if (!visit[neighbor])
                dfs(AorB, neighbor, v);
        }
    }
}

bool isConnected(vector<bool> &v){
    memset(visit, false, sizeof(visit));
    dfs(0, A[0], v);
    for (int i=0; i<A.size(); i++){
        if (!visit[A[i]])
            return false;
    }
    memset(visit, false, sizeof(visit));
    dfs(1, B[0], v);
    for (int i=0; i<B.size(); i++){
        if (!visit[B[i]])
            return false;
    }
    return true;
}

void solve(){
    for (int i=1; i<=(N/2); i++){
        vector<bool> v(N-i, false);
        v.insert(v.end(), i, true);
        do{
            A.clear(); B.clear();
            for (int k=0; k<N; k++){
                if (v[k])
                    A.push_back(k+1);
                else
                    B.push_back(k+1);
            }
            if (isConnected(v)){
                ans=min(ans, abs(calc(A)-calc(B)));
            } 
        } while (next_permutation(v.begin(), v.end()));
    }
}

int main() {
	int num, x;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> populations[i];
	}
	for (int i = 1; i <= N; i++) {
		cin >> num;
		for (int j = 0; j < num; j++) {
			cin >> x;
			adj[i].push_back(x);
		}
	}
    solve();
	if (ans != INT_MAX)
		cout << ans << "\n";
	else
		cout << -1 << "\n";

	return 0;
}

완전 탐색(조합)+DFS 문제.

 

조합을 이용해 가능한 모든 수에 대해 (N개 중 1개, 2개.. N/2개 뽑는 경우의 수), 두 선거구를 나눈다. 

두 선거구가 서로 연결되어있는지 체크한다.

서로 연결되어 있는 것은 DFS 탐색을 통해 한다. DFS 탐색을 할 때에는 "미방문 노드" 이면서, "자기 선거구에 속한 이웃 구역" 인 것을 탐색한다. 자기 선거구에 속한 구역의 방문 여부를 체크하여, 방문이 모두 완료되었을 때==선거구의 구역이 모두 연결된 것이다. 이것을 A, B 선거구 모두에 대해 해준다. 

 

두 선거구 모두 구역 간 서로 연결이 되어 있는 경우, 인구수를 각각 계산해주어 그 차를 구해줘 min으로 비교해서 답을 내면 된다.