[BOJ] 17471. 게리맨더링

조합과 그래프탐색을 하는 시뮬레이션 문제이다.

이 문제를 접근할때 단순하게 생각하여 접근하였다. 일단 모든 도시들의 연결관계를 그래프를 이용하여 나타내주었고, 그후 도시들을 조합으로 1개부터 N/2개를 만큼 선택을 하였다. 그 후 같은 팀이된 도시들끼리 DFS로 이어져있는지 확인하였고 만일 같은팀이 전부 이어져있는 형태를 그린다면 그때의 인구수 차이를 체크해주었다.

다양한 것을 구현해야하고 구현하는 서순이 복잡하지만 천천히 하나씩 구현해보았다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main_bj_17471_게리맨더링 {
    
    static List<Integer>[] list;
    static int[] people;
    
    static int N;
    
    static int[] arr;
    static boolean[] visitForComb;
    static int[] pick;
    
    static boolean[] visitForDFS;
    
    static List<Integer> team1;
    
    static int calc;
    static int answer;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        N=Integer.parseInt(br.readLine());
        people=new int[N];
        arr=new int[N];
        list=new ArrayList[N];
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++) {
            people[i]=Integer.parseInt(st.nextToken());
            arr[i]=i;
            list[i]=new ArrayList<>();
        }
        
        
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            int n=Integer.parseInt(st.nextToken());
            for(int j=0;j<n;j++) {
                list[i].add(Integer.parseInt(st.nextToken())-1);
            }
        }
        
        answer=Integer.MAX_VALUE;
        for(int i=1;i<=N/2;i++) {
            visitForComb=new boolean[N];
            pick=new int[i];
            comb(0,0,i);
        }
        if(answer==Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(answer);
    }
    
    static void comb(int start,int depth,int dest) {
        if(depth==dest) {
//            System.out.println(Arrays.toString(pick));
            if(check()==true) {
                answer=Math.min(answer, calc);
            }
            return;
        }
        
        for(int i=start;i<N;i++) {
            if(visitForComb[i]==false) {
                visitForComb[i]=true;
                pick[depth]=arr[i];
                comb(i,depth+1,dest);
                visitForComb[i]=false;
            }
        }
        
    }
    
    static boolean check() {
        team1=new ArrayList<>();
        for(int p : pick) {
            team1.add(p);
        }
        
        int team1start=-1;
        int team2start=-1;
        
        for(int i=0;i<N;i++) {
            if(team1.contains(i)==true) {
                team1start=i;
            }else {
                team2start=i;
            }
            if(team1start!=-1 && team2start!=-1)
                break;
        }
 
        visitForDFS=new boolean[N];
        
        dfs(team1start,true);
        dfs(team2start,false);
 
        for(int i=0;i<N;i++) {
            if(visitForDFS[i]==false) {
                return false;
            }
        }
        
        int sum1=0;
        int sum2=0;
        
        for(int i=0;i<N;i++) {
            if(team1.contains(i)==true)
                sum1+=people[i];
            else
                sum2+=people[i];
        }
        
        calc=Math.abs(sum1-sum2);
        
        return true;
    }
    
    static void dfs(int cur,boolean flag) {
        visitForDFS[cur]=true;
        
        for(int next : list[cur]) {
            if(visitForDFS[next]==false && team1.contains(next)==flag) {
                dfs(next,flag);
            }
        }
        
    }
    
    
}