BJ17471 게리맨더링

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

모든 조합을 확인해 선거구를 선택된 것과 그렇지 않은 것 두가지 그룹으로 나누고, 각 선거구가 연결되었는지 BFS를 통해 확인하고 최솟값을 비교하여 갱신한다.

package day0406;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Gerrymandering {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static boolean[][] adjMatrix;
	static int[] weight, numbers, gB;
	static int N, min, sumofWeight;

	static void combi(int cnt, int start, int sum) {

		if (Math.abs(sumofWeight - sum * 2) < min && groupcheck(numbers, cnt) && groupcheck(calcGB(cnt), N - cnt)) {
			min = Math.abs(sumofWeight - sum * 2);
		}

		for (int i = start; i < N; i++) {
			numbers[cnt] = i;
			combi(cnt + 1, i + 1, sum + weight[i]);
		}
	}

	static int[] calcGB(int cnt) {
		boolean[] selected = new boolean[N];
		int[] result = new int[N];
		for (int i = 0; i < cnt; i++) {
			selected[numbers[i]] = true;
		}
		int tmp_cnt = 0;
		for (int i = 0; i < N; i++) {
			if (!selected[i]) {
				result[tmp_cnt++] = i;
			}
		}
		return result;
	}

	static boolean groupcheck(int[] A, int cnt) {
		boolean[] c = new boolean[N];
		Queue<Integer> q = new LinkedList<Integer>();
		c[A[0]] = true;
		q.offer(A[0]);
		int cnt_t = 1;
		int n;
		while (!q.isEmpty()) {
			n = q.poll();
			for (int i = 0; i < cnt; i++) {
				if (!adjMatrix[n][A[i]] || c[A[i]])
					continue;
				q.offer(A[i]);
				c[A[i]] = true;
				cnt_t++;
			}
		}
		if (cnt_t == cnt) {
			return true;
		}
		return false;
	}

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		weight = new int[N];
		adjMatrix = new boolean[N][N];
		sumofWeight = 0;
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			weight[i] = Integer.parseInt(st.nextToken());
			sumofWeight += weight[i];
		}
		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++) {
				adjMatrix[i][Integer.parseInt(st.nextToken()) - 1] = true;
			}
		}
		numbers = new int[N];
		min = Integer.MAX_VALUE;
		combi(0, 0, 0);
		if(min == Integer.MAX_VALUE) bw.append("-1");
		else bw.append(min + "");
		bw.flush();
	}
}