[BOJ] 17471 - 게리맨더링(JAVA)

문제

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

17471번: 게리맨더링

 

풀이

각각의 선거구를 미리 할당한 부분집합을 구한 뒤, 그래프 탐색을 돌리면서 부분집합과 모순이 없는지 확인하면 되는 문제이다.

만약, bfs로 탐색했을 때, 탐색하지 못한 구역이 있다면, 구역이 분리되어 있으므로 불가능한 경우가 된다.

 

최적화된 부분집합을 구하기 위해서 비트마스크 기법을 사용했다.

두 집합으로 나뉘지 않는 경우를 제거하기 위해 1부터 시작했으며, 01010(2)와 10101(2)와 같이 집합의 순서에 따른 결과는 차이가 없기 때문에 1<<(n-1)까지 탐색한다.

 

가장 먼저, 그래프를 구성한 뒤, 모든 구역을 탐색하며, 처음 만나는 그룹에 대해서만 bfs를 돌리므로, 총 2번 돌리게 된다.

 

코드

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

public class Main {

	static List<Integer>[] graph;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer tk = new StringTokenizer(br.readLine());
		int[] population = new int[n];
		for(int i=0; i<n; i++) {
			population[i] = Integer.parseInt(tk.nextToken());
		}
		graph = new ArrayList[n];
		for(int i=0; i<n; i++) {
			graph[i] = new ArrayList<>();
			tk = new StringTokenizer(br.readLine());
			int c = Integer.parseInt(tk.nextToken());
			for(int cnt=0; cnt<c; cnt++) {
				graph[i].add(Integer.parseInt(tk.nextToken())-1);
			}
		}
		int answer = -1;
		
		loop:
		for(int bitmask = 1; bitmask<(1<<(n-1)); bitmask++) {

			//red = bit가 1, blue = bit가 2
			int[] visited = new int[n];
			
			int redCnt = 0;
			for(int i=0; i<n; i++) {
				//bit가 활성화된 곳들에서 1로 바꾸는 bfs 탐색을 한바퀴 돌린다.
				if(getColor(i,bitmask)==1 && visited[i]!=1) {
					bfs(visited,i,1,bitmask);
					break;
				}
			}
			for(int i=0; i<n; i++) {
				//bit가 활성화된 곳들에서 2로 바꾸는 bfs 탐색을 한바퀴 돌린다.
				if(getColor(i,bitmask)==2 && visited[i]!=2) {
					bfs(visited,i,2,bitmask);
					break;
				}
			}
			int red = 0;
			int blue = 0;
			//만약 결과가 bitmask와 다르다면 false
			for(int i=0; i<n; i++) {
				if(visited[i]==0) continue loop;
				if(visited[i] == 1) red += population[i];
				else blue += population[i];
			}
			int result = Math.abs(red-blue);
			if(answer == -1) answer = result;
			else if(result < answer) answer=  result;
		}
		System.out.print(answer);
	}
	static void bfs(int[] visited, int node, int color, int bitmask) {

		visited[node] = color;
		for(int nextNode : graph[node]) {
			if(visited[nextNode]==color || getColor(nextNode,bitmask)!=color) continue;
			bfs(visited,nextNode, color, bitmask);
		}
		return ;
	}
	static int getColor(int node, int bitmask) {
		if((bitmask&(1<<node))!=0) return 1;
		else return 2;
	}
}