[백준] 17471번 게리맨더링 (java, bfs, subset)

www.acmicpc.net/problem/17471

17471번: 게리맨더링

subset으로 집합을 나눈다.

vis[번호]=true => a집합, false면 b집합 

 

만약 리스트 두 개를 만들어서 각각 집어넣는다. 

 

리스트 하나라도 길이가 0이다 => 나머지 몰빵 => 집합 2개가 안됨 => return

리스트 두 개의 길이를 합쳤는데 n이 안됨 => 집합이 3개 이상이라는 뜻 =>  return 

 

그 다음에는 한 집합 내에서  bfs로 인접리스트를 돌리며 한 집합의 모든 원소가 연결되는 지 확인한 후 

두 집합 합의 차이를 구해준다.

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int n,m;
	static ArrayList<Integer>[] area;
	static int[] people;
	static boolean[] vis;
	static int answer=Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		area=new ArrayList[n+1];
		people=new int[n+1];
		for (int i = 1; i <=n; i++) {
			area[i]=new ArrayList<>();
		}
		for (int i = 1; i <=n; i++) {
			people[i]=sc.nextInt();
		}
		for (int i = 1; i <=n; i++) {
			m=sc.nextInt();
			for (int j = 0; j < m; j++) {
				int another=sc.nextInt();
				area[i].add(another);
				area[another].add(i);
			}
		}
		vis=new boolean[n+1];
		// 두 개의 선거구로 나눔.
		subset(1);//1부터 시작
		System.out.println(answer==Integer.MAX_VALUE?-1:answer);
		
	}
	
	private static void subset(int cnt) {
		if(cnt==n) {
			ArrayList<Integer> a=new ArrayList<>();
			ArrayList<Integer> b=new ArrayList<>();
			for (int i = 1; i <=n; i++) {
				if(vis[i]) {
					a.add(i);
				}
				else b.add(i);
			}
			if(a.size()+b.size()!=n)return;//3개  이상일때 
			if(a.size()==0 || b.size()==0)return;//집합이 2개가 안될 때
			if(isPossible(a,'a') && isPossible(b,'b')) {
				int sum=0;
				for (int i = 0; i < a.size(); i++) {
					sum+=people[a.get(i)];
				}
				int sum2=0;
				for (int i = 0; i < b.size(); i++) {
					sum2+=people[b.get(i)];
				}
				answer=Math.min(answer, Math.abs(sum-sum2));
			}
			
			return;
		}
		vis[cnt]=true;//a집합 
		subset(cnt+1);
		vis[cnt]=false;
		subset(cnt+1);//b집합 
		
	}
	

	private static boolean isPossible(ArrayList<Integer> a,char team) {
		boolean[] connect=new boolean[n+1];//같은 팀이 모두 연결되었나 본다.
			int cur=a.get(0);//현재 번호
			Queue<Integer> q=new LinkedList<Integer>();
			q.add(cur);
			connect[cur]=true;
			while(q.size()!=0) {
				int temp=q.poll();
				for (int j = 0; j < area[temp].size(); j++) {
					int next=area[temp].get(j);//temp와 연결된 번호
					if(connect[next])continue;//방문된거 pass
					if((team=='a' && vis[next]) ||(team=='b' && vis[next]==false)) {//같은 팀이라면
						q.add(next);
						connect[next]=true;
					}
				}
			}
		
		
		for (int i = 0; i < a.size(); i++) {
			if(!connect[a.get(i)])return false;//같은 집합내 연결 안된애가 있다면 false
		}
		return true;
	}
}