[BOJ] 17471. 게리맨더링

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	static Scanner sc=new Scanner(System.in);
	static int N,max,total,visitCnt;
	static int pop[];
	static boolean check[];
	static boolean visit[];
	static List<Integer> list=new ArrayList<Integer>();
	static List<Integer> list2=new ArrayList<Integer>();
	static List<Integer> vertex[];
	static boolean flag1,flag2;
	public static void main(String[] args) {
		init();
		go(0,1,0);
		if(max==Integer.MAX_VALUE) {
			System.out.println(-1);
		}else {
			System.out.println(max);
		}
	}
	
	public static void go(int d,int st,int sum) {
		if(d>5) return;
		if(d<=5) {
			if(d!=0) {
				int size=list.size();
				visitInit();
				for (int i = 1; i <= N; i++) {
					if(check[i]) continue;
					list2.add(i);
				}
				visitCnt=0;
				if(list.size()!=0) {
					dfs(list.get(0),0,list);
					if(visitCnt==list.size()) flag1=true;
				}
				visitCnt=0;
				if(list2.size()!=0) {
					dfs(list2.get(0),0,list2);
					if(visitCnt==list2.size()) flag2=true;
				}
				if(flag1 && flag2) {
					int team2=total-sum;
					int diff=sum-team2;
					diff=(diff>0)?diff:-diff;
					if(max>diff) {
						max=diff;
					}
				}
				flag1=false;
				flag2=false;
				list2.clear();
			}
		}
		if(d==5) return;
		
		for (int i = st; i <= N; i++) {
			if(!check[i]) {
				check[i]=true;
				list.add(i);
				go(d+1,i,sum+pop[i]);
				list.remove(list.size()-1);
				check[i]=false;
			}
		}
	}
	
	public static void dfs(int v,int d,List<Integer> list) {
		visit[v]=true;
		visitCnt++;
		for (int i = 0; i < vertex[v].size(); i++) {
			int nv=vertex[v].get(i);
			if(!visit[nv] && list.contains(nv)) {
				dfs(nv,d+1,list);
			}
		}
	}
	
	public static void init() {
		N=sc.nextInt();
		max=Integer.MAX_VALUE;
		pop=new int[N+1];
		check=new boolean[N+1];
		visit=new boolean[N+1];
		vertex=new List[N+1];
		for (int i = 1; i <= N; i++) {
			vertex[i]=new ArrayList<Integer>();
		}

		for (int i = 1; i <= N; i++) {
			pop[i]=sc.nextInt();
			total+=pop[i];
		}
		
		int cnt=1;
		for (int i = 0; i < N; i++) {
			int e=sc.nextInt();
			for (int j = 0; j < e; j++) {
				int v=sc.nextInt();
				vertex[cnt].add(v);
			}
			cnt++;
		}
	}
	
	public static void visitInit() {
		for (int i = 1; i <= N; i++) {
			visit[i]=false;
		}
	}
}