[백준] 17471 - 게리맨더링

[문제링크]

17471번: 게리맨더링

 

0. 인구의 수는 항상 양수이므로, 모든 구역이 한쪽 선거구에 속할 경우는 고려하지 않아도 된다

  - N:0의 인구의 차이는, N-1:1의 인구의 차이보다 항상 클 테니까

 

1. 모든 선거구의 부분집합 S을 구한다(sub함수)

 

2. S에 속한 한 선거구, S에 속하지 못한 한 선거구를 선택해, 각각 bfs를 실행한다

  - bfs를 돌며 선거구의 개수와 그 인구수를 누적한다

 

3. 두 bfs의 결과 선거구의 합이 전체 선거구의 합과 같다면, 잘 연결된 두개의 선거구가 존재한다는 것

  - 누적한 인구의 차이를 반환한다

 

4. 3 결과값의 최종 최솟값을 출력한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
	
	static int N, min;
	static int[]people;
	static boolean[][]adj;
	static Queue<Integer>pick = new LinkedList<Integer>();
	static Queue<Integer>nonpick = new LinkedList<Integer>();
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = pint(br.readLine());
		min=Integer.MAX_VALUE;
		people=new int[N];
		adj=new boolean[N][N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) people[i] = pint(st.nextToken());
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			st.nextToken();
			while(st.hasMoreTokens()) adj[i][pint(st.nextToken())-1]=true;
		}
		
		sub(0, 0);
		System.out.println(min==Integer.MAX_VALUE? -1 : min);
		
	}
	
	static void sub(int cnt, int mask) {
		if(cnt==N) {
			//mask : 선택한 노드
			min=Math.min(bfs(mask), min);
			return;
		}
		sub(cnt+1, mask|1<<cnt);
		sub(cnt+1, mask);
	}
	
	static int bfs(int mask) {
		//bfs두번 실행, 모든 노드를 탐색하는가?
		int s1=-1, s2=-1;
		for (int i = 0; i < N; i++) {
			if((mask&1<<i)!=0)s1=i; // 1인 노드 중 아무거나
			else s2=i; // 0인 노드 중 아무거나
		}
		
		int cnt1=0, total1=0, temp=mask;
		if(s1!=-1) {
			pick.offer(s1);
			temp^=1<<s1; // 방문 노드 삭제
			total1+=people[s1];
			cnt1++;
		}
		while(!pick.isEmpty()) {
			int cur = pick.poll();
			
			for (int i = 0; i < N; i++) {
				//가본적 없고, 연결되있으면
				if((temp&1<<i)!=0 && adj[cur][i]) {
					pick.offer(i);
					temp^=1<<i; // 방문 노드 삭제
					total1+=people[i];
					cnt1++;
				}
			}
		}
		
		int cnt2=0, total2=0; temp=mask;
		if(s2!=-1) {
			nonpick.offer(s2);
			temp^=1<<s2; // 방문 노드 삭제
			total2+=people[s2];
			cnt2++;
		}
		while(!nonpick.isEmpty()) {
			int cur = nonpick.poll();
			
			for (int i = 0; i < N; i++) {
				//가본적 없고, 연결되있으면
				if((temp&1<<i)==0 && adj[cur][i]) {
					nonpick.offer(i);
					temp^=1<<i; // 방문 노드 삭제
					total2+=people[i];
					cnt2++;
				}
			}
		}
		if(cnt1+cnt2==N)return Math.abs(total1-total2);
		else return Integer.MAX_VALUE;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면