[Baekjoon Online Judge] 17471 - 게리맨더링 / Java

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

17471번: 게리맨더링

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

public class Main {
	// 구역의 수
	static int N;

	// 구역의 인구
	static int[] population;

	// 인접 행렬
	static boolean[][] adjMatrix;

	// 선거구 인구 차이의 최솟값
	static int minDiff = Integer.MAX_VALUE;

	// 구역 체크 true: A, false: B
	static boolean[] isAreaA;

	// 구역 연결 여부 확인 시 사용
	static boolean[] validCheck;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());

		// 구역의 인구 입력 받기
		population = new int[N + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			population[i] = Integer.parseInt(st.nextToken());
		}

		// 간선 정보 입력
		adjMatrix = new boolean[N + 1][N + 1];
		// n: 인접한 구역의 수
		int n = 0, to = 0;
		for (int from = 1; from <= N; from++) {
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());

			for (int i = 0; i < n; i++) {
				to = Integer.parseInt(st.nextToken());
				adjMatrix[from][to] = true;
			}
		}

		// 선거 구역 나누기
		// N / 2: 1개 뽑는 조합과 N-1개 뽑는 조합의 인구 차의 값은 동일하므로
		for (int i = 1; i <= N / 2; i++) {
			isAreaA = new boolean[N + 1];
			combination(0, 1, i);
		}

		System.out.println(minDiff == Integer.MAX_VALUE ? -1 : minDiff);
	}

	// r: 뽑는 개수
	private static void combination(int cnt, int start, int r) {
		// 선거구 선택 완료한 경우
		if (cnt == r) {
			// 선거구 연결 여부 확인
			if (!isVaild()) {
				return;
			}

			// 선거구 인구 차이 계산
			int diff = getDiff();

			// 최솟값 갱신
			minDiff = Math.min(minDiff, diff);

			return;
		}

		for (int i = start; i <= N; i++) {
			// A 선거구인 경우
			if (isAreaA[i]) {
				continue;
			}

			// A 선거구로 선택
			isAreaA[i] = true;
			combination(cnt + 1, i, r);
			// 다음 선택 위해 되돌리기
			isAreaA[i] = false;
		}
	}

	private static boolean isVaild() {
		// 선거구 연결 확인

		validCheck = new boolean[N + 1];

		// A 구역 확인
		for (int i = 1; i <= N; i++) {
			// A 구역의 정점일 경우
			if (isAreaA[i]) {
				dfs(i, true);
				break;
			}
		}

		// B 구역 확인
		for (int i = 1; i <= N; i++) {
			// B 구역의 정점일 경우
			if (!isAreaA[i]) {
				dfs(i, false);
				break;
			}
		}

		// 모두 방문했는지 확인
		for (int i = 1; i <= N; i++) {
			// 방문하지 못한 곳이 있다면 연결되지 않은 것이므로 false
			if (!validCheck[i]) {
				return false;
			}
		}

		// 모두 방문했다면 연결되어 있으므로 true
		return true;
	}

	private static void dfs(int from, boolean area) {
		validCheck[from] = true;

		for (int to = 1; to <= N; to++) {
			// 이동가능하고 같은 선거구이고 방문하지 않은 곳이라면
			if (adjMatrix[from][to] && isAreaA[to] == area && !validCheck[to]) {
				dfs(to, area);
			}
		}
	}

	private static int getDiff() {
		int aPop = 0;
		int bPop = 0;

		for (int i = 1; i <= N; i++) {
			// A구역이라면
			if (isAreaA[i]) {
				aPop += population[i];
			}
			// B구역이라면
			else {
				bPop += population[i];
			}
		}

		return Math.abs(aPop - bPop);
	}
}