[Java] 백준 17471번 : 게리맨더링

1. 문제

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

17471번: 게리맨더링

 

 

 

2. 풀이과정

 

1. 팀 나누기(조합)

조합의 특성을 이용하자면, 아래 문제에서 nC1과 nC(n-1)은 같은 경우라고 볼 수 있다. 따라서 n/2개까지만 뽑는 조합을 작성하여 simulation을 돌린다.

 

왜 같은 경우인지 설명하자면, 두 팀으로 나누어 두 팀의 값 차이를 결과로 내기 때문에, 각 팀이 빨간팀인지 파란팀인지는 상관없다. 빨간팀의 값이 1이고 파란팀이 3일 때와 빨간팀의 값이 3이고 파란팀이 1일 때 두 차이값은 같다.

 

 

2. 연결 확인

같은 팀이고 연결이 있다면, 그 연결을 따라가는 과정을 bfs로 작성하였다.

 

 

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

public class Boj17471 {
	static int N, su[], result, total, conn[][];
	static boolean selected[];
	//1개~N/2개까지 뽑는 조합
	public static void combination(int start, int cnt, int sum) {//조합 선택 시작점, 선택한 개수, 선택한 수들의 합
		if(1<=cnt && cnt<=N/2) {
			int gap = Math.abs(sum - (total-sum));//차이 = sum과 (총합 - sum)의 차이값
			if(result > gap) {//최솟값보다 크면 볼 필요 없음
				if(isConnected(true, cnt) && isConnected(false, N-cnt)) {
					result = gap;//연결돼있다면 갱신
				}
			}	
			if(cnt==N/2) {//최대 N/2까지 뽑고 stop
				return;
			}
		}
		
		for(int i=start; i<N; i++) {
			selected[i] = true;
			combination(i+1, cnt+1, sum+su[i]);
			selected[i] = false;
		}
	}
	
	public static boolean isConnected(boolean b, int cnt) {
		if(cnt==1) {//1개면 true반환
			return true;
		}
		
		boolean visited[] = new boolean[N];
		Queue<Integer> queue = new LinkedList<>();
		//처음으로 b와 일치하는 값 찾아서 queue에 넣어주기
		for(int i=0;i<N;i++) {
			if(selected[i] == b) {
				visited[i] = true;
				queue.offer(i);
				break;
			}
		}
		cnt--;
		
		while(!queue.isEmpty()) {
			int n = queue.poll();
			for(int i=0;i<N;i++) {//값이 b이고, 연결된 상태이며, 방문하지 않았다면 방문하자
				if(selected[i]==b && conn[n][i] == 1 && !visited[i]) {
					visited[i] = true;
					cnt--;
					queue.offer(i);
				}
			}
		}
		
		if(cnt==0) {//b인 값을 모두 방문했으면 true반환
			return true;
		}
		else {
			return false;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		final int INF = 999_999_999;
		N = Integer.parseInt(br.readLine());//구역 수
		su = new int[N];//인구 수
		selected = new boolean[N];//구역 나누기 true/false
		conn = new int[N][N];
		total = 0;
		result = INF;
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			su[i] = Integer.parseInt(st.nextToken());
			total += su[i];
		}
		//인접matrix 받기
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			int cnt = Integer.parseInt(st.nextToken());
			for(int j=0;j<cnt;j++) {
				conn[i][Integer.parseInt(st.nextToken())-1] = 1;
			}
		}
		
		combination(0, 0, 0);
		if(result == INF) {
			System.out.println(-1);
		}
		else{
			System.out.println(result);
		}
	}
}