[JAVA] 백준 17471 게리맨더링

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

17471번: 게리맨더링

 

import java.util.*;
import java.io.*;

public class Main {

	static int N, total=0, min = Integer.MAX_VALUE;
	static int[] people;
	static ArrayList<Integer>[] graph;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		people = new int[N+1];
		graph = new ArrayList[N+1];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			int val = Integer.parseInt(st.nextToken());
			people[i] = val;
			total += val;
			
			graph[i] = new ArrayList<>();
		}
		
		for(int i=1; i<=N;i++) {
			st = new StringTokenizer(br.readLine());
			int cnt = Integer.parseInt(st.nextToken());
			while(cnt-->0) {
				int val = Integer.parseInt(st.nextToken());
				graph[i].add(val);
			}
		}
		
		for(int i=1; i<=N/2;i++) {	
			comb(i, 0, 1, new int[N+1]);
		}
		
		System.out.println(min==Integer.MAX_VALUE?-1:min);
	}

	
	public static void comb(int num, int cnt, int start, int[] select) {
		if(cnt==num) {
			if(check(select)) {
				int sum = 0;
				for(int i=1; i<=N; i++) {
					if(select[i]==1) {
						sum += people[i];
					}
				}
				min = Math.min(min, Math.abs((total-sum)-sum));
			}
			return;
		}
		
		for(int i=start; i<=N; i++) {
			select[i] = 1;
			comb(num, cnt+1, i+1, select);
			select[i] = 0;
		}
	}
	
	public static boolean check(int[] select) {
		boolean[] visit = new boolean[N+1];
		
		for(int i=1; i<=N; i++) {
			if(select[i]==0) {
				dfs(visit, select, i, 0);
				break;
			}
		}
		
		for(int i=1; i<=N; i++) {
			if(select[i]==1) {
				dfs(visit, select, i, 1);
				break;
			}
		}
		
		for(int i=1; i<=N; i++) {
			if(visit[i]==false) return false;
		}
		
		return true;
	}
	
	public static void dfs(boolean[] visit, int[] select, int cur, int part) {
		visit[cur] = true;
		
		for(int i=0;i<graph[cur].size(); i++) {
			int next = graph[cur].get(i);
			if(!visit[next] && select[next]==part) dfs(visit, select, next, part);
		}
	}
}