17471 번 : 게리맨더링 [Java]

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

17471번: 게리맨더링

 

해결 방안

1. 인접 행렬을 만든다.

2. 선거구를 둘로 나눈다.

3. 같은 그룹에 있는 선거구들끼리 연결되어있는지 확인한다.

4. 연결되지 않았다면 -1 출력, 연결되었다면 두 그룹 차이의 최솟값을 저장

 

전체 코드

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

public class Main {
	static int N;
	static int[] arrP;
	static int sumP;
	static int[][] map;
	static boolean[] isSelected;
	static int ans = Integer.MAX_VALUE;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(input.readLine()); // 구역의 개수
		arrP = new int[N + 1];
		StringTokenizer st = new StringTokenizer(input.readLine(), " ");
		for (int i = 1; i <= N; i++) { // 구역 별 인구
			arrP[i] = Integer.parseInt(st.nextToken());
			sumP += arrP[i];
		}

		map = new int[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(input.readLine(), " ");
			int n = Integer.parseInt(st.nextToken());
			for (int j = 0; j < n; j++) {
				map[i][Integer.parseInt(st.nextToken())] = 1;
			}
		}

		isSelected = new boolean[N + 1];
		calc(1, 0);

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

	private static void calc(int idx, int sum) {
		if (idx > N) {
			// 두 선거구가 잘 나누어졌는가 => 잘 나누어졌다면 인구차의 최솟값을 저장하자
			if (connected(true) && connected(false))
				ans = Math.min(ans, Math.abs(sum - (sumP - sum)));

			return;
		}

		isSelected[idx] = true;
		calc(idx + 1, sum + arrP[idx]);
		isSelected[idx] = false;
		calc(idx + 1, sum);
	}

	private static boolean connected(boolean b) {

		// 같은 그룹에 있는 선거구들이 연결되어있는가 확인하자
		boolean visited[] = new boolean[N + 1];
		LinkedList<Integer> list = new LinkedList<Integer>();

		// 처음을 넣는다.
		for (int i = 1; i <= N; i++) {
			if (isSelected[i] == b) {
				list.addLast(i);
				visited[i] = true;
				break;
			}
		}

		while (!list.isEmpty()) {
			int cur = list.poll();
			for (int i = 1; i <= N; i++) {
				// 같은 그룹에 속해있고, 둘이 연결되어있으며, 방문한적이 없다면
				if (isSelected[i] == b && map[cur][i] == 1 && !visited[i]) {
					list.addLast(i);
					visited[i] = true;
				}
			}
		}

		// 같은 그룹인데 방문한 적이 없다면 => 연결되지 않은 상태
		for (int i = 1; i <= N; i++) {
			if (isSelected[i] == b && !visited[i])
				return false;
		}
		return true;
	}
}