[백준] 17471. 게리맨더링

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

17471번: 게리맨더링

---

N 개의 구역이 있으면 1 ~ N-1 개의 뽑을 수 있는 모든 구역을 뽑아서 두 가지를 판단 합니다.

① 뽑힌 선거구가 연결 되어 있는지  ② 뽑힌 선거구를 제외한 나머지 선거구들이 연결 돼 있는지

두 가지 조건을 만족하면 각 선거구들의 포함된 인구수를 구해서 차이값을 계속 비교하면서 최소를 구합니다. 제가 처음에 썻던 조합코드는 중복 때문에 시간초과가 나왔는데, 제가 정리했던 https://daily-life-of-bsh.tistory.com/139?category=784825 주사위 던지기1 문제에서 3번 모두 다른 수가 나올 경우의 코드를 이용해서 시간초과를 해결했습니다.

[ 문제 풀이 ]

1. 2차원 배열에 각 선거구와 연결된 선거구들을 입력받습니다.

2. 1개의 구역 ~ N-1 개의 구역을 뽑아서 뽑힌 구역 번호를 areaA에 제외한 나머지 구역번호를 areaB에 차례대로 저장합니다.

3. 그리고 areaA먼저 DFS하여 1차원 boolean 배열 visited를 가지고 연결되어 있는지 확인하고 areaB를 마찬가지로 진행합니다. 원래 DFS 와 다른점은 2 번째 매개변수로 int[] area를 받아서 DFS를 할 때 반복문을 통해서 area를 돌면서 연결되어 있는지 확인하는 것입니다. 이렇게 하면 매개변수에 areaA와 B를 넣어서 하나의 DFS로 연결되어 있는지 판단할 수 있습니다.

4. 2개의 구역 다 연결되어있으면 인구수의 차를 계산하여 최소값을 구합니다.

---

import java.util.Scanner;

// 17471 게리맨더링

public class Main {
	static int N, d, answer = Integer.MAX_VALUE;
	static int[] people;
	static int[][] arr;
	static int[] temp, areaA, areaB;
	static boolean[] visited, mask;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new int[N+1][];
		people = new int[N+1];

		for(int i=1; i<=N; i++) people[i] = sc.nextInt();
		
		for(int i=1; i<=N; i++) {
			int area = sc.nextInt();
			arr[i] = new int[area];
			for(int j=0; j<area; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		
		
		
		for(int i=1; i<N; i++) {
			temp = new int[N+1];
			mask = new boolean[N+1];
			temp[0] = 1;
			d = i;
			recur(1, 0);
		}
		
		if(answer == Integer.MAX_VALUE) System.out.println("-1");
		else System.out.println(answer);
		
	}
	
	public static void recur(int start, int depth) {
		if(depth == d) {
			
//			for(int i=1; i<=d; i++) {
//				System.out.print(temp[i] + " ");
//			}
//			System.out.println();
			
			areaA = new int[d];
			areaB = new int[N-d];
			
			boolean[] check = new boolean[N+1];
			
			for(int i=1; i<=d; i++) {
				areaA[i-1] = temp[i];
				check[temp[i]] = true;
			}
			
			int idx = 0;
			for(int i=1; i<=N; i++) if(!check[i]) areaB[idx++] = i;
			
			visited = new boolean[N+1];
			DFS(areaA[0], areaA);
			for(int i=1; i<=d; i++) if(!visited[areaA[i-1]]) return;
		
			
			visited = new boolean[N+1];
			DFS(areaB[0], areaB);
			for(int i=1; i<=N-d; i++) if(!visited[areaB[i-1]]) return;
			
			
			int sumA = 0;
			int sumB = 0;
			for(int i=1; i<=d; i++) sumA += people[areaA[i-1]];
			for(int i=1; i<=N-d; i++) sumB += people[areaB[i-1]];
			
			answer = Math.min(Math.abs(sumA-sumB), answer);
			
			return;
		}
		for(int i=temp[start-1]; i<=N; i++) {
			if(mask[i]) continue;
			temp[start] = i;
			mask[i] = true;
			recur(start+1, depth+1);
			mask[i] = false;
		}
	}
	
	public static void DFS(int x, int[] area) {
		visited[x] = true;
		
		for(int i=0; i<arr[x].length; i++) {
			
			int nx = arr[x][i];
			
			if(!visited[nx]) {
				for(int j=0; j<area.length; j++) {
					if(area[j] == nx) DFS(nx, area );
				}
			}
		}
	}
}