[백준] 17471 게리맨더링 - JAVA

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

17471번: 게리맨더링

 

 

[풀이]

• 조합 + BFS + 구현(시뮬레이션) 
• 1. 두개의 선거구 각각에 포함될 구역을 정한다. - 조합 
• 2. 각각의 선거구에 포함된 구역들이 서로 연결되어 있는지 확인한다. - BFS 
• 3. 연결되어 있다면 인구수 차이, 그렇지 않다면 적당히 큰 값을 리턴한다. 

---

 

[구현 과정]

• int num[] : 각 구역의 인구 수 
• List<ArrayList<Integer>> graph : 각 구역의 연결정보 저장 
• boolean select[] : 조합을 구현하는 과정에서 해당 구역이 선택되었는지 체크하는 배열 
• min : 인구 수의 최솟값 (=최종값) 
  (모든 구역의 인구 총합의 최댓값이 1000이므로 1000으로 지정) 

 

1. N개의 구역의 각 연결정보를 입력받아 graph 에 저장한다. (인덱스는 편의상 0~N-1로 바꿔주었다.) 

 

2. 각각의 선거구에 포함될 구역을 찾기 위해 1~N/2개의 구역을 조합을 통해 고른다. 
(N/2개까지인 이유는 (2,4)로 나누는 것과 (4,2)로 나누는 것은 같기 때문이다.) 

💡 cnt개의 조합을 다 찾게 되면 select 배열에는 true인 구역 cnt개와, 나머지 false로 나누어진다. 

 

 

3. cnt 개의 조합을 구하였다면 두 구역의 인구 수 차이를 구한다. select 배열에서 true 값을 가진 구역과 false 값을 가진 구역을 각각 first, second 리스트에 넣는다. 

 

4. BFS 탐색을 통해 first / second 리스트 각각의 구역이 서로 연결되어 있는지 확인한다. 

 

5. 두 구역다 서로 연결 되어 있다면, 두 구역의 인구 총합 차이를 반환한다. 하나라도 연결되어 있지 않다면 1000을 반환한다. 

 

6. 모든 조합의 경우를 따져 최솟값을 갱신한 후, 최솟값이 아직도 1000이라면 -1 출력, 그렇지 않다면 min 값을 출력. 

 

---

 

[소스 코드]

import java.util.*;
import java.io.*;

public class Main {
	static int N;
	static int num[];
	static List<ArrayList<Integer>> graph = new ArrayList<>(); 
	static boolean select[]; //선택된 구역
	static int min = 1000; 
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st; 
		
		N = Integer.parseInt(br.readLine()); //구역의 갯수 
		num = new int[N];
		select= new boolean[N]; 
		for(int i=0; i<=N; i++) graph.add(new ArrayList<>()); 
		
		st= new StringTokenizer(br.readLine(), " "); 
		for(int i=0; i<N; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=0; i<N; i++) {
			st= new StringTokenizer(br.readLine(), " "); 
			int n = Integer.parseInt(st.nextToken()); 
			while(n-- >0) {
				int next= Integer.parseInt(st.nextToken())-1; 
				graph.get(i).add(next);
			}
		}
		for(int i=1; i<=N/2; i++) {
			select(0, i); //N개 중에 i개 고르기 
		}
		
		if(min == 1000) System.out.println(-1);
		else System.out.println(min);
 	
	}//end of main
	
	private static void select(int index, int cnt) {
		//가능한지, 인구차이 몇인지 찾으러 ㄱㄱ 
		if(cnt==0) {
			min = Math.min(min, calSub(select)); 
			
			return; 
		}
		
		for(int i=index; i<N; i++) {
			select[i] = true; 
			select(i+1, cnt-1); 
			select[i] = false; 
		}
	}
	
	private static int calSub(boolean[] select) {
		List<Integer> first= new ArrayList<>(); 
		List<Integer> second= new ArrayList<>(); 
		int first_sum=0;
		int second_sum=0; 
		for(int i=0; i<N; i++) {
			if(select[i]) {
				first.add(i);
				first_sum += num[i]; 
			}
			else {
				second.add(i); 
				second_sum += num[i]; 
			}
		}
		
		//두 구역 다 서로 다 연결되어있어야 함 
		if(isConnected(first) && isConnected(second)) {
			return Math.abs(first_sum - second_sum); 
		}
		//하나라도 연결 안되어있으면 
		else return 1000;  
	}
    
	//리스트에 담겨있는 구역이 모두 연결되어있는지 확인하는 메소드 
	private static boolean isConnected(List<Integer> list) {
		Queue<Integer> que = new LinkedList<>();
		boolean visited[] = new boolean [N];
		visited[list.get(0)] = true;
		que.add(list.get(0)); 
		
		int count =1; //리스트에 있는 곳 다 갔는지 확인하기 위한 변수 
		while(!que.isEmpty()) {
			int node= que.poll();
			for(int next : graph.get(node)) {
				//같은 구역에 있는 곳이고 아직 방문안한 곳이면, 
				if(!visited[next] && list.contains(next)) {
					visited[next] = true; 
					que.add(next); 
					count ++; 
				}
			}
		}
		
		if(count != list.size()) return false;  
		return true; 
	}
}//end of class