BOJ - 17471 ) 게리맨더링

---

 

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

17471번: 게리맨더링

 

---

상당히 쫄았던 문제이다.. 

Union-Find 개념을 이용하여 접근하려니 접근방법이 잘 보이지 않았고, 워스트케이스에대해서 0.5초의 시간을

넘을 것같다는 생각이 들었다.

 

일단한번 서브셋을 구해서 나누어보자! 라는 생각으로 접근하였는데, 단순한 2번의 BFS로 해결되었다.

문제에 쫄면 안되겠다.

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_게리멘더링 {
	static boolean visit[];
	static ArrayList<Integer> node[];
	static int cost[] ,answer = Integer.MAX_VALUE,T, c[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		T = Integer.parseInt(st.nextToken());
		node = new ArrayList[T];  
		// 그래프들을 연결하는 Node를 ArrayList로 선언한다.
		cost = new int[T]; 
		st = new StringTokenizer(br.readLine());
		
		for(int index = 0 ;index <T ; index++) {
			cost[index] = Integer.parseInt(st.nextToken());
			node[index] = new ArrayList<Integer>();
		
		// 각 노드의 비용 ( 선거구 인원 ) 과 ArrayList를 초기화해준다.
		}
		for(int index=0 ; index <T ; index++) {
			st = new StringTokenizer(br.readLine());
			int loop = Integer.parseInt(st.nextToken());
			for(int i = 0 ; i < loop ; i++ ) {
				int t = Integer.parseInt(st.nextToken());
				node[index].add(t-1);
				// 입력을 받아서 연결시켜준다.
			}
		}
		
		for(int i = 0 , size = (1<<T) ;i < size ; i++ ) {
			c = new int[T];
			// 0과 1로 이루어진 서브셋을 구한다.
			// 0 이면 0끼리 연결되었다 생각하고 1은 1끼리 연결되었다 생각하여 해당 그래프에서 
			// 그 Index까지 갈수있는지? 를 확인한다.
			for(int j = 0 ; j <=T ; j++) {
				if((i & (1 << j)) !=0 ) {
					c[j]=1;
				}
			}
			
			if(judge(c)) {
				// Judge 함수는 010101 이 있다면 인덱스로 접근하여 1 3 5가 연결되어있는지 , 2 4 6 이 연결되어
				// 있는지를 판단하는 함수
				// 나눌수 있다면 최소 금액을 계산
				int sum1=0,sum2=0;
				for(int index = 0 ; index < T ; index++) {
					if(c[index]==1) {sum1 += cost[index];}
					else {sum2 += cost[index];}}
				answer = Math.min(answer, Math.abs(sum1-sum2));
			}
		}
		answer = answer == Integer.MAX_VALUE ? -1 : answer;
		System.out.print(answer);
	}
	public static boolean judge(int c[]) {
		visit = new boolean[T];
	 
		int zero_first = -1 , one_first = -1;
		for(int index = 0 ;index < c.length ; index++) {
			if(zero_first < 0 && c[index] ==0)zero_first=index;
			if(one_first < 0  && c[index] ==1)one_first=index;
		}
		
		if(zero_first ==-1 || one_first == -1) return false;
		ArrayDeque<Integer> dq = new ArrayDeque<>();
		// 0 인것만 체크
		dq.add(zero_first);
		visit[zero_first] = true;
		while(!dq.isEmpty()) {
			int now = dq.poll();
			for(int index = 0 ; index < node[now].size(); index++) {
				if(!visit[node[now].get(index)] &&  c[node[now].get(index)] ==0) {
					visit[node[now].get(index)] = true;
					dq.add(node[now].get(index));
				}
			}
		}
		
		dq.add(one_first);
		visit[one_first] = true;
		while(!dq.isEmpty()) {
			int now = dq.poll();
			for(int index = 0 ; index < node[now].size(); index++) {
				if(!visit[node[now].get(index)] && c[node[now].get(index)] == 1) {
					visit[node[now].get(index)] = true;
					dq.add(node[now].get(index));
				}
			}
		}
		for (boolean b : visit) {
			// 중간에 건너 뛰어서 false인것이 있다면
			// 그 그래프는 연결되지 않은것임
			if(!b)return false;
		}
		return true;
	}

}

---