[백준] 17471. 게리맨더링 (Java)

 

문제

17471번: 게리맨더링

 

알고리즘

그래프, 조합론, 너비우선탐색(BFS)

 

풀이

선거구를 두 개로 나누기 때문에 한 선거구에 포함될 지역을 구하고, 나머지는 모두 다른 선거구에 포함하면 된다.

또한, 선거구에 포함될 지역의 개수 제한이 없기 때문에 한 선거구의 지역 조합은 {} ~ {1,2,3...N}으로 1~N개의 부분 집합이 된다.

 

따라서 

1. 부분 집합을 구하고,

2. 선거구를 나누고,

3. 유효한 선거구인지 확인하고,

4. 선거구에 포함된 지역의 인구 수 합의 차이를 구해 최솟값을 갱신한다.

 

이때, 유효한 선거구의 조건에는 다음 두 가지가 있다.

1. 선거구는 적어도 하나 포함해야 한다.

2. 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.

 

이를 나타낸 함수 구조는 다음과 같다.

void powerSet (int count) {
	
	if(count == N + 1) {
		
		// 선거구 나누기
		
		// 어느 한 선거구가 비어있다면 return
		// 두 선거구 중 하나라도 연결되어있지 않다면 return

		// 최솟값 구하여 갱신
		return;
	}

	selected[count] = true;
	powerSet(count + 1);
	selected[count] = false;
	powerSet(count + 1);
}

 

선거구 나누기는 visited 가 true 라면 1 선거구 리스트에, 아니라면 2 선거구 리스트에 넣는 식으로 진행하고

한 선거구가 비어있는 지는 각 선거구 리스트가 비어있는 지 확인하면 된다.

 

각 선거구가 연결되어있는 지 확인하는 것이 핵심인데 이때, 너비우선탐색(BFS)를 이용하였다.

선거구가 연결되어있는 것까지 확인했다면, 유효한 선거구이므로 배열에 저장한 각 구역의 인구 수를 통해 인구 수 차이의 최솟값을 갱신한다.

 

처음 최솟값을 Integer.MAX_VALUE로 두고, 함수 반환이 끝난 후 갱신된 적 없이 그대로 Integer.MAX_VALUE라면 -1을 출력한다.

 

코드

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

public class Main {
	static int N, min, citizen[];
	static ArrayList<Integer>[] graph;
	static boolean[] selected;

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

		N = Integer.parseInt(br.readLine());
		graph = new ArrayList[N + 1];
		citizen = new int[N + 1];
		selected = new boolean[N + 1];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= N; i++) {
			graph[i] = new ArrayList<>();
			citizen[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			int n = Integer.parseInt(st.nextToken());
			for (int j = 0; j < n; j++) {
				int a = Integer.parseInt(st.nextToken());
				graph[i].add(a);
			}
		}

		min = Integer.MAX_VALUE;
		subset(1);

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

	static void subset(int count) {

		if (count == N + 1) {

			// 선거구 나누기
			ArrayList<Integer> group1 = new ArrayList<>();
			ArrayList<Integer> group2 = new ArrayList<>();

			for (int i = 1; i <= N; i++) {
				if (selected[i]) group1.add(i);
				else group2.add(i);
			}

			// 어느 한 선거구가 비어있다면 return
			if (group1.isEmpty() || group2.isEmpty()) return;
			
			// 두 선거구 중 하나라도 연결되어있지 않다면 return
			if (!check(group1) || !check(group2)) return;

			// 최솟값 구하여 갱신
			min = Math.min(min, Math.abs(getTotal(group1) - getTotal(group2)));
			return;
		}

		selected[count] = true;
		subset(count + 1);
		selected[count] = false;
		subset(count + 1);
	}

	private static boolean check(ArrayList<Integer> group) {

		boolean[] visited = new boolean[N + 1];
		ArrayDeque<Integer> deque = new ArrayDeque<>();
		deque.add(group.get(0));
		visited[group.get(0)] = true;

		while (!deque.isEmpty()) {
			int cur = deque.poll();

			for (int next : graph[cur]) {
				if (!group.contains(next) || visited[next]) continue;

				visited[next] = true;
				deque.add(next);
			}
		}

		for (int num : group) {
			if (!visited[num])
				return false;
		}

		return true;
	}

	static int getTotal(ArrayList<Integer> group1) {
		int sum = 0;
		for (int num : group1)
			sum += citizen[num];
		return sum;
	}
}