[BaekJoon] 17471 게리멘더링 (Java)

1.  문제 링크

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

2.  문제

요약

• 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있습니다.

• 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 합니다.

• 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 합니다.

• 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, A, B 두 구역은 연결되어 있다고 합니다.

• 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 합니다.

• 공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 합니다.

• 백준시의 정보가 주어졌을 때, 인구 차이의 최솟값을 구하는 문제입니다.

• 입력: 첫 번째 줄에 2보다 크거나 같고 10보다 작거나 같은 구역의 개수 N이 주어지고 두 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어집니다. 세 번째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어집니다. 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고 이후 인접한 구역의 번호가 주어집니다.

  • 구역 A가 구역 B와 인접하면 구역 B도 구역 A와 인접합니다. 인접한 구역이 없을 수도 있습니다.

• 출력: 첫 번째 줄에 백준시를 두 선구거로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력합니다. 두 선거구로 나눌 수 없는 경우에는 -1을 출력합니다.

3.  소스코드

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

public class Main {
	static int N, result = Integer.MAX_VALUE;
	static int[] population;
	static ArrayList<Integer>[] map;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		population = new int[N + 1];
		map = new ArrayList[N + 1];
		for(int area = 1; area <= N; area++) {
			population[area] = scanner.nextInt();
			map[area] = new ArrayList<>();
		}
		for(int area = 1; area <= N; area++) {
			int num = scanner.nextInt();
			for(int count = 1; count <= num; count++) {
				int neighbor = scanner.nextInt();
				map[area].add(neighbor);
			}
		}
	}
	
	static void solution() {
		ArrayList<Integer> list = new ArrayList<>();
		for(int size = 1; size <= N / 2; size++) makeList(1, size, list);
		if(result == Integer.MAX_VALUE) result = -1;
		System.out.println(result);
	}
	
	static void makeList(int start, int size, ArrayList<Integer> list) {
		if(size == 0) {
			calcPopulation(list);
			return;
		}
		for(int area = start; area <= N; area++) {
			list.add(area);
			makeList(area + 1, size - 1, list);
			list.remove(list.size() - 1);
		}
	}
	
	static void calcPopulation(ArrayList<Integer> list) {
		if(!isConnected(list.get(0), list, list.size())) return;
		ArrayList<Integer> list2 = new ArrayList<>();
		for(int area = 1; area <= N; area++) {
			if(list.contains(area)) continue;
			list2.add(area);
		}
		if(!isConnected(list2.get(0), list2, list2.size())) {
			return;
		}
		int p1 = 0;
		for(int index = 0; index < list.size(); index++)
			p1 += population[list.get(index)];
		int p2 = 0;
		for(int index = 0; index < list2.size(); index++)
			p2 += population[list2.get(index)];
		int dif = Math.abs(p1 - p2);
		result = Math.min(result, dif);
	}
	
	static boolean isConnected(int area, ArrayList<Integer> list, int size) {
		boolean[] visited = new boolean[N + 1];
		visited[area] = true;
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.offer(area);
		int count = 1;
		while(!queue.isEmpty()) {
			int cur = queue.poll();
			for(int neighbor : map[cur]) {
				if(!visited[neighbor] && list.contains(neighbor)) {
					visited[neighbor] = true;
					count++;
					queue.offer(neighbor);
				}
			}
		}
		if(count == size) return true;
		return false;
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}