[17471] 게리맨더링 - Java[자바]

 

| 문제 링크

 

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

17471번: 게리맨더링

 

 

 

 

---

 

 

 

 

| 문제

 

 

1. 게리맨더링이란 선거구를 자기 정당에 유리하도록 구획하는 일입니다.
   미국은 여러 주로 이루어져있어 단순히 인원수로 투표하는 방식이 아니라 게리맨더링이 사용된다고 합니다.
2. 구역의 개수 N이 주어지며, N개의 구역에 인구수는 1이상 100이하 입니다(2 ≤ N ≤ 10).
3. 구역별 연결된 구역이 주어지며, 구역별로 이어진 2개의 선거구로 구획하였을 때, 두 선거구의 인구 차이의 최소값을 출력하시오.
   두 선거구로 나눌 수 없는 경우에는 -1을 출력합니다.

 

 

 

---

 

 

 

| 풀이

 

 

1. 인접리스트를 생성해 구역별로 이어진 구역을 나타냅니다.
2. 크기가 N+1인 boolean 배열을 생성해 true, false로 구역을 구분합니다(0번 인덱스는 사용하지 않음).
3. dfs를 사용해 2번 배열에 대해 모든 부분 조합을 구합니다.
4. 3번에서 depth가 N일 때, 아래의 조건을 확인하는 반환 값이 boolean인 메서드를 만듭니다.
   1) 모든 구역이 true나 false로 이루어져있을 경우 false
   2) true 구역이 이어져있지 않을 경우 false
   3) false 구역이 이어져있지 않을 경우 false
   세 가지 조건을 모두 통과한 경우 true 반환
5. 4번 메서드의 반환값이 true인 경우 true 지역과 false 지역의 합의 중 최소를 구합니다.

 

 

 

 

---

 

 

 

 

| 코드

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static int N;
	public static int min = Integer.MAX_VALUE;
	public static int[] popul;
	public static boolean[] flag;
	public static List<Integer>[] graph;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		popul = new int[N+1];
		graph = new ArrayList[N+1];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i<=N; i++) {
			popul[i] = Integer.parseInt(st.nextToken());
			graph[i] = new ArrayList<>();
		}
		
		//인접리스트 만들기
		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 num = Integer.parseInt(st.nextToken());
				graph[i].add(num);
			}
		}
		
		flag = new boolean[N+1];
		dfs(0);
		if(min == Integer.MAX_VALUE)
			bw.write("-1");
		else
			bw.write(String.valueOf(min));
		br.close();
		bw.close();
		
	}
	
	public static void dfs(int depth) {
		//조합 선택 완료
		if(depth == N) {
			//부분 조합으로 완성된 구역들이 연결되었는지 확인
			if(link()) {
				int a = 0;
				int b = 0;
				for(int i = 1; i<=N; i++) {
					if(flag[i])
						a+=popul[i];
					else
						b+=popul[i];
				}
				
				min = Math.min(min, Math.abs(a-b));
				
			}
			return;
		}
		flag[depth] = true;
		dfs(depth+1);
		flag[depth] = false;
		dfs(depth+1);
		
	}
	
	//구역들이(true, false로 구분) 연결되었는지
	public static boolean link() {
		int cnt = 0;
		for(int i = 1; i<=N; i++)
			if(flag[i])
				cnt++;
		
		//구역이 나누어져있지 않다면 false
		if(cnt==0 || cnt==N)
			return false;
		
		boolean[] check = new boolean[N+1];
		Queue<Integer> que = new LinkedList<>();
		
		//true인 구역을 한 군데 정해 연결되어 있는지 확인
		for(int i = 1; i<=N; i++) {
			if(flag[i]) {
				que.add(i);
				check[i] = true;
				break;
			}
		}
		
		while(!que.isEmpty()) {
			int node = que.poll();
			for(int i : graph[node]) {
				if(check[i])
					continue;
				if(!flag[i])
					continue;
				check[i] = true;
				que.add(i);
			}
		}
		//flase인 구역을 한 군데 정해 연결되어 있는지 확인
		for(int i = 1; i<=N; i++) {
			if(!flag[i]) {
				que.add(i);
				check[i] = true;
				break;
			}
		}
		
		while(!que.isEmpty()) {
			int node = que.poll();
			for(int i : graph[node]) {
				if(check[i])
					continue;
				if(flag[i])
					continue;
				check[i] = true;
				que.add(i);
			}
		}
		
		for(int i = 1; i<=N; i++) {
			if(!check[i])
				return false;
		}
		
		return true;
		
	}

}