백준 : 17471

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

17471번: 게리맨더링

 

package com.ssay.algo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B17471 {
	public static int N;
	public static int population[];
	public static int Map[][];
	public static int minValue;
	public static boolean check[];

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		population = new int[N + 1];
		Map = new int[N + 1][N + 1];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int n = 1; n <= N; n++) {
			population[n] = Integer.parseInt(st.nextToken());
		}

		for (int n = 1; n <= N; n++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			for (int i = 0; i < a; i++) {
				int v = Integer.parseInt(st.nextToken());
				Map[n][v] = 1;
				Map[v][n] = 1;

			}
		}
		

		minValue = Integer.MAX_VALUE;
		check = new boolean[N + 1];
		Combi(0, 1);

		if (minValue == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(minValue);
		}
	}

	public static int confirmation;
	public static boolean dfsCheck[];

	public static void Combi(int cnt, int s) {
		if (cnt > 0) {

			int start = 0;
			for (int n = 1; n <= N; n++) {
				if (check[n]) {
					start = n;
					break;
				}
			}

			confirmation = 0;
			boolean Redcheck = true;
			dfsCheck = new boolean[N + 1];
			isPossible(start, true);
			if (confirmation != cnt)
				Redcheck = false;
			
			for (int n = 1; n <= N; n++) {
				if (!check[n]) {
					start = n;
					break;
				}
			}
			
			confirmation = 0;
			dfsCheck = new boolean[N + 1];
			isPossible(start, false);
			
			boolean Bluecheck = true;
			if (confirmation != N - cnt)
				Bluecheck =false;

			if(Bluecheck && Redcheck) {
				int Blue = 0;
				int Red = 0;
				for (int n = 1; n <= N; n++) {
					if (check[n]) {
						Red += population[n];
					} else {
						Blue += population[n];
					}
				}
				
				if (minValue > Math.abs(Red - Blue)) {
					minValue = Math.abs(Red - Blue);
				}
				
			}

			if (cnt == N / 2) {
				return;				
			}
		}

		for (int i = s; i <= N; i++) {
			if (!check[i]) {
				check[i] = true;
				Combi(cnt + 1, i + 1);
				check[i] = false;
			}
		}
	}

	public static void isPossible(int n, boolean myCheck) {
		
		confirmation++;
		dfsCheck[n] = true;
		for (int i = 1; i <= N; i++) {
			if (dfsCheck[i])
				continue;
			if (Map[n][i] == 0)
				continue;
			if (check[i] != myCheck)
				continue;
			
			isPossible(i, myCheck);
		}

	}
}