[백준] G5 17471 게리맨더링 (java)

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

17471번: 게리맨더링

 

풀이

 

0) 준비물

• 최소 차이를 저장할 int 형 변수 minChai = Integer.MAX_VALUE
• 인접리스트 graph[]

1) 조합으로 N개중 1개~N/2 개 뽑는 모든 경우를 구한다.

2) 1)에서 나온 조합으로 팀을 가른다.

3) 갈라진 팀이 연결되어있지 않다면 다음 조합으로 넘어간다.

4) 갈라진 팀이 연결되어 있다면 각 팀의 인구수 차이를 구하여 최소 차를 갱신한다.

5) 모든 경우에서 가장 작은 최소차를 출력한다. 만약 Integer.MAX_VALUE일 경우 두 선거구로 나눌 수 없는 경우다. -1

 

주의사항

 

1) 문제를 똑바로 읽자.

2) 5C2개를 뽑는것과 3개를 뽑는경우는 같은 경우이다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G5_17471_게리맨더링 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N, population[], result[], minChai = Integer.MAX_VALUE, groups[];
	static List<Integer> graph[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		N = Integer.parseInt(input.readLine());
		population = new int[N+1];
		graph = new List[N+1];
		for(int i=0; i<N+1; i++) {
			graph[i] = new ArrayList<>();
		}
		tokens = new StringTokenizer(input.readLine());
		for(int i=1; i<N+1; i++) {
			population[i] = Integer.parseInt(tokens.nextToken());
		}
		for(int i=1; i<N+1; i++) {
			tokens = new StringTokenizer(input.readLine());
			tokens.nextToken();
			while(tokens.hasMoreTokens()) {
				graph[i].add(Integer.parseInt(tokens.nextToken()));
			}
		} // 입력 끝
		
		result = new int[N+1]; // 조합 결과를 담을 배열.
		for(int i=1; i<=N/2; i++) {
			grouping(1,0,i); 
		}
		if(minChai == Integer.MAX_VALUE) {
			System.out.println(-1);
		}else {
			System.out.println(minChai);
		}
	}

	private static void grouping(int start, int cnt, int R) { // 1이면 1팀 0이면 0팀
		if(cnt == R) {
//			System.out.println(Arrays.toString(result));
			checkLink(); // 연결되어 있는지 확인.
//			System.out.println(minChai);
//			System.out.println();
			return;
		}
		for(int i=start; i<=N; i++) {
			result[i] = 1;
			grouping(i+1, cnt+1, R);
			result[i] = 0;
		}
	}

	private static void checkLink() {
		groups = new int[2];
		boolean isConnected = true; // 연결상태가 정상인지 확인하는 변수
		
		// bfs를 2번 돌아 1팀과 0팀이 각각 연결된 상태인지 확인한다. 
		for(int i=1; i<N+1; i++) {
			if(result[i] == 1) {
				if(!bfs(i, 1)) {
					isConnected = false;
				}
				break;
			}
		}
		for(int i=1; i<N+1; i++) {
			if(result[i] == 0) {
				if(!bfs(i, 0)) {
					isConnected = false;
				}
				break;
			}
		}
		if(isConnected) {
//			System.out.println(Arrays.toString(groups));
			if(minChai > Math.abs(groups[0] - groups[1])) {
				minChai = Math.abs(groups[0] - groups[1]);
			}
		}
	}

	private static boolean bfs(int start, int party) {
		boolean isVisited[] = new boolean[N+1];
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(start);
		isVisited[start] = true;
		int sum = 0;
		while(!queue.isEmpty()) {
			Integer front = queue.poll();
			sum += population[front];
			List<Integer> childs = graph[front];
			for(int i=0; i<childs.size(); i++) {
				Integer child = childs.get(i);
				if(!isVisited[child] && result[child] == party){ // 연결된 구역이 뽑은 구역인지 확인
					isVisited[child] = true;
					queue.offer(child);
				}
			}
		}
		for(int i=1; i<N+1; i++) {
			if(result[i] == party && !isVisited[i]) { // 연결 실패
				return false;
			}
		}
		groups[party] = sum;
		return true;
	}

	static String src =
			"10\r\n" + 
			"43 21 32 4 54 9 12 35 76 81\r\n" + 
			"3 5 6 8\r\n" + 
			"3 5 7 9\r\n" + 
			"4 4 5 8 10\r\n" + 
			"3 3 5 9\r\n" + 
			"8 1 2 3 4 6 7 8 9\r\n" + 
			"3 1 5 7\r\n" + 
			"3 2 5 6\r\n" + 
			"3 1 3 5\r\n" + 
			"3 2 4 5\r\n" + 
			"1 3";
}

 

후기

 

 문제의 입력에서

"셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다. 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다. 모든 값은 정수로 구분되어져 있다." <- 이부분을 똑바로 읽지 않고 첫번째 정수도 인접한 구역이라고 생각했다. 하..

문제를 똑바로 읽자..