[BOJ 17471] 게리맨더링 (Java)

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

17471번: 게리맨더링

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

public class Main_BOJ_17471 {
	static int N;
	static int[] population;
	static int[][] adjList;
	static boolean[] visited;
	static int answer=Integer.MAX_VALUE;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		N=Integer.parseInt(br.readLine());
		population=new int[N+1];
		adjList=new int[N+1][];
		st=new StringTokenizer(br.readLine());
		for (int i=1; i<N+1; i++) {
			population[i]=Integer.parseInt(st.nextToken());
		}
		for (int i=1; i<N+1; i++) {
			st=new StringTokenizer(br.readLine());
			int len=Integer.parseInt(st.nextToken());
			adjList[i]=new int[len];
			for (int j=0; j<len; j++) {
				adjList[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		for (int i=1; i<=N/2; i++) {
			comb(1, 0, i, new int[N+1]);
		}
		System.out.println(answer==Integer.MAX_VALUE?-1:answer);
	}
	
	private static void comb(int begin, int cnt, int target, int[] picked) {
		if (cnt==target) {
			int[] a=new int[target];
			int[] b=new int[N-target];
			int acnt=0, bcnt=0;
			for (int i = 1; i < picked.length; i++) {
				if (picked[i]==1) a[acnt++]=i;
				else b[bcnt++]=i;
			}
			visited=new boolean[N+1];
			dfs(a[0], picked, 1);
			if (check(a.length)) {
				visited=new boolean[N+1];
				dfs(b[0], picked, 0);
				if (check(b.length)) {
					answer=Math.min(Math.abs(calc(a)-calc(b)), answer);
				}
			}
			return;
		}
		for (int i=begin; i<=N; i++) {
			picked[i]=1;
			comb(i+1, cnt+1, target, picked);
			picked[i]=0;
		}
	}

	private static int calc(int[] arr) {
		int cnt=0;
		for (int i = 0; i < arr.length; i++) {
			cnt+=population[arr[i]];
		}
		return cnt;
	}

	private static boolean check(int total) {
		int cnt=0;
		for (int i = 1; i<N+1; i++) {
			if (visited[i]) cnt++; 
		}
		return total==cnt ? true: false;
	}

	private static void dfs(int num, int[] picked, int val) {
		visited[num]=true;
		for (int i=0; i<adjList[num].length; i++) {
			int neighbor=adjList[num][i];
			if (!visited[neighbor] && picked[neighbor]==val) {
				dfs(neighbor, picked, val);
			}
		}
	}

}

1. N개의 구역 중 nC1, nC2, .. nCn/2  까지 뽑는 경우의 수를 구한다.

2. 각 경우의 수에서 동일한 선거구 안에 속한 구역이 서로 간 연결되었는지 체크한다

3. 서로 간 연결되었다면 인구수 차이를 구해 답안을 갱신한다

 

연결성 체크 부분에서 조금 깔끔하지 못하게 풀었다.

dfs를 통해 탐색해서 방문한 곳(미방문한 곳이며 & 각 구역에 속한 지역일것)의 수를 visited 배열을 순회하면서 센다.

그 후 센 값이 각 선거구 안에 속한 지역의 수와 같으면 연결되었다고 간주한다. 

 

다른 분들의 코드를 보니 BFS 로 풀면 더 깔끔해진다. (https://steady-coding.tistory.com/33)

BFS를 통해 방문 가능한 곳을 큐에 넣어주면서, 큐 안에 들어간 구역의 수를 세어주면 연결성을 체크할 수 있다.

아래 코드는 DFS 대신 BFS 를 이용한 코드.

 

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

public class Main_BOJ_17471 {
	static int N;
	static int[] population;
	static int[][] adjList;
	static boolean[] visited;
	static int answer=Integer.MAX_VALUE;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		N=Integer.parseInt(br.readLine());
		population=new int[N+1];
		adjList=new int[N+1][];
		st=new StringTokenizer(br.readLine());
		for (int i=1; i<N+1; i++) {
			population[i]=Integer.parseInt(st.nextToken());
		}
		for (int i=1; i<N+1; i++) {
			st=new StringTokenizer(br.readLine());
			int len=Integer.parseInt(st.nextToken());
			adjList[i]=new int[len];
			for (int j=0; j<len; j++) {
				adjList[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		for (int i=1; i<=N/2; i++) {
			comb(1, 0, i, new int[N+1]);
		}
		System.out.println(answer==Integer.MAX_VALUE?-1:answer);
	}
	
	private static void comb(int begin, int cnt, int target, int[] picked) {
		if (cnt==target) {
			int[] a=new int[target];
			int[] b=new int[N-target];
			int acnt=0, bcnt=0;
			for (int i = 1; i < picked.length; i++) {
				if (picked[i]==1) a[acnt++]=i;
				else b[bcnt++]=i;
			}
			if (bfs(a[0], picked, a.length, 1) && bfs(b[0], picked, b.length, 0)) {
				answer=Math.min(Math.abs(calc(a)-calc(b)), answer);
			}
			return;
		}
		for (int i=begin; i<=N; i++) {
			picked[i]=1;
			comb(i+1, cnt+1, target, picked);
			picked[i]=0;
		}
	}

	private static boolean bfs(int begin, int[] picked, int length, int val) {
		visited=new boolean[N+1];
		Queue<Integer> q=new LinkedList<>();
		int cnt=0;
		q.add(begin);
		cnt++;
		visited[begin]=true;
		while (!q.isEmpty()) {
			int curr=q.poll();
			for (int i=0; i<adjList[curr].length; i++) {
				int neighbor=adjList[curr][i];
				if (!visited[neighbor] && picked[neighbor]==val) {
					visited[neighbor]=true;
					q.add(neighbor);
					cnt++;
				}
			}
		}
		if (cnt==length) return true;
		return false;
	}

	private static int calc(int[] arr) {
		int cnt=0;
		for (int i = 0; i < arr.length; i++) {
			cnt+=population[arr[i]];
		}
		return cnt;
	}

	

}