[백준] 17471 게리맨더링

 

완탐으로 풀 수 있어서 dfs를 이용해 풀었다

팀을 나눈 후 그래프로 표현하고 dfs를 이용해

내가 우리팀에 갈 수 있는지 체크를 하면 된다

 

여기서 만약 애초에 그래프가 2개 이상의 연결요소로 구성되어있다면 

애초에 2개의 팀으로 나눌 수 없어서 -1 을 출력하고 종료하자!

 

그럼 그래프를 그린 후를 생각해보자

dfs를 이용해서 origin -> next 로 갈 수 있는지 계속 확인해보며 된다

그 후 만약 같은 팀인데 연결 되어있지않다면 false 아니면 true를 리턴해주고

만약 모든 조건을 만족한다면 팀의 합의 최소를 구해보자

 

 

소스코드 (C++)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
int n,ans=1e9;
int cnt[11];
bool connect[11][11];
bool check[11],Team[11];
 
vector<vector<int>> Graph;
 
void dfs(int origin,int x){
    check[x]=true;
 
    for(int i=0;i<Graph[x].size();i++){
        int next = Graph[x][i];
        if(!check[next] && (Team[origin]==Team[next])){
            connect[origin][next]=connect[next][origin]=true;
            dfs(origin,next);
        }
    }
}
 
bool can(){
    memset(connect,0,sizeof(connect));
    for(int i=0;i<n;i++){
        memset(check,0,sizeof(check));
        dfs(i,i);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j) continue;
            if((Team[i]==Team[j]) && !connect[i][j]) return false;
        }
    }
    return true;
}
 
int main(){
    scanf(" %d",&n);
    Graph.resize(n);
    for(int i=0;i<n;i++) scanf(" %d",&cnt[i]);
    for(int i=0;i<n;i++){
        int m; scanf(" %d",&m);
        for(int j=0;j<m;j++){
            int k; scanf(" %d",&k); k--;
            Graph[i].push_back(k);
            Graph[k].push_back(i);
        }
    }
 
    int c=0;
    for(int i=0;i<n;i++) if(!check[i]) dfs(i,i),c++;
    if(c>2){
        puts("-1"); return 0;
    }
    for(int i=1;i<(1<<n)-1;i++){
        memset(Team,0,sizeof(Team));
        int Asum=0,Bsum=0;
        for(int j=0;j<n;j++){
            if(i&(1<<j)) Team[j]=true,Asum+=cnt[j];
            else Bsum+=cnt[j];
        }
        if(can()) ans = min(ans,abs(Asum-Bsum));
    }
 
    printf("%d\n",ans);
}