백준 / 그래프 / 17471번 / 게리맨더링 / Java

< 문제 바로가기 >

17471번: 게리맨더링

 

package boj.p17471;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	private static StringTokenizer st = null;
	
	/** 구역의 개수 */
	private static int N;
	/** 각 구역의 인구 */
	private static int[] populationList;
	/** 인접 리스트 */
	private static LinkedList<Integer>[] adjList;
	
	/** true와 false로 나뉜 두 구역 */
	private static boolean[] divide;
	
	/** 인구 차이의 최솟값 */
	private static int minDistance;

	public static void main(String[] args) throws Exception {
		input();
		solve();
		print();
	}

	private static void input() throws Exception {
		N = Integer.parseInt(br.readLine());
		
		populationList = new int[N + 1];
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++) {
			populationList[i] = Integer.parseInt(st.nextToken());
		}
		
		adjList = new LinkedList[N + 1];
		for(int i=1; i<=N; i++) {
			adjList[i] = new LinkedList<>();
		}
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			
			int n = Integer.parseInt(st.nextToken());
			for(int j=1; j<=n; j++) {
				adjList[i].add(Integer.parseInt(st.nextToken()));
			}
		}
		
		br.close();
	}
	
	private static void solve() {
		minDistance = Integer.MAX_VALUE;
		divide = new boolean[N + 1];
		
		getMinDistance(1);
	}
	
	private static void getMinDistance(int idx) {
		// 모든 구역을 끝까지 탐색하여 조합을 구성한 경우,
		if(idx == N + 1) {
			for(int i=1; i<=N; i++) {
				// true인 구역끼리 이어지는지 검사한다.
				if(divide[i] == true) {
					if(isConnected(i, true) == false) {
						return;
					}
					// 모두 이어져 있어야 하기 때문에 한번만 검사해도 된다.
					break;
				}
			}
			for(int i=1; i<=N; i++) {
				// false인 구역끼리 이어지는지 검사한다.
				if(divide[i] == false) {
					if(isConnected(i, false) == false) {
						return;
					}
					// 모두 이어져 있어야 하기 때문에 한번만 검사해도 된다.
					break;
				}
			}
			
			int area1 = 0; // true 구역의 인구수
			int area2 = 0; // false 구역의 인구수
			
			// 각 구역의 인구수를 세준다.
			for(int i=1; i<=N; i++) {
				if(divide[i] == true) {
					area1 += populationList[i];
				}
				else {
					area2 += populationList[i];
				}
			}
			
			int distance = Math.abs(area1 - area2);
			// 최소값 갱신한다.
			minDistance = Math.min(minDistance, distance);
			
			return;
		}
		
		for(int i=idx; i<=N; i++) {
			if(divide[i] == true) {
				continue;
			}
			
			divide[i] = true;
			getMinDistance(i + 1);
			divide[i] = false;
		}
	}
	
	/**
	 * 조합으로 구한 두 나뉘어진 선거구가 같은 선거구끼리 이어지는지 검사하는 함수
	 * 
	 * @param start 시작 구역
	 * @param flag 구역
	 * @return
	 */
	private static boolean isConnected(int start, boolean flag) {
		int flagCnt = 0;
		// 인자로 들어온 flag에 해당하는 선거구 내부의 구역의 개수를 세준다.
		for(int i=1; i<=N; i++) {
			if(divide[i] == flag) {
				flagCnt++;
			}
		}
		
		Deque<Integer> stack = new ArrayDeque<>();
		boolean[] isVisited = new boolean[N + 1];
		
		isVisited[start] = true;
		stack.push(start);
		
		while(!stack.isEmpty()) {
			int cur = stack.pop();
			flagCnt--;
			
			for(int next : adjList[cur]) {
				if(isVisited[next] == true) {
					continue;
				}
				if(divide[next] != flag) {
					continue;
				}
				
				isVisited[next] = true;
				stack.push(next);
			}
		}
		
		// 모두 이어져 있다면 true를 반환한다.
		return flagCnt == 0;
	}

	private static void print() throws Exception {
		// 두 선거구로 나눌 수 없는 경우에는 초기값 그대로 있으므로, -1로 바꿔준다.
		if(minDistance == Integer.MAX_VALUE) {
			minDistance = -1;
		}
		
		bw.write(minDistance + "");
		bw.flush();
		bw.close();
	}
}