[BOJ] Q17471 게리맨더링

🔗문제 링크

BOJ 17471번

🔒 문제 설명

1 ~ N번 구역이 있다. 구역을 두개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에만 포함 되어야 한다. 또한 같은 선거구의 구역은 서로 연결 되어 있어야 한다.

공평한 선거가 되기위하여 두 선거구에 포함된 인구의 차이를 최소로 하려고할 때 인구차이의 최솟값을 구하라.

🧾 입력 예시

6
5 2 3 4 1 2
2 2 4
4 1 3 6 5
2 4 2
2 1 3
1 2
1 2

첫째 줄에는 구역의 갯수 N이 주어진다.

둘째 줄에는 각 구역의 인구수가 주어진다.

셋째 줄부터는 각 구역의 번호와 인접한 구역의 정보가 주어진다. 처음 정수는 해당 구역의 번호이고 이후 정수들은 인접한 구역의 번호이다.

🔎 출력 예시

1

🔑 문제 풀이

1. 각 구역의 인구수를 담을 population배열과 각 구역의 연결 상태를 담을 map 2차원 배열을 생성한다.

2. 1번 구역과 2번구역이 연결되어 있다면 ,map[1][2]=1, map[2][1]=1로 갱신한다.

3. 한 선거구의 구역 수가 1 부터 N/2 까지 각 경우에 대하여 dfs를 통하여 구역을 설정한다. (N/2 이후 경우는 중복이므로 제외시킴)

4. dfs 메소드에서 dep==len의 경우, visited가 true인 선거구과 false인 선거구들이 인접한지 확인하기 위하여 canGo메소드를 작성하여 사용한다.

5. 두 선거구 모두 인접하였다면 각 선거구의 인구수의 차이를 계산하여 ret를 갱신한다.

💻 전체 코드

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

public class Q17471_Gerrymandering {
	public static void main(String[] args) throws NumberFormatException, IOException {
		Main z = new Main();
		z.solution();
	}
	int N = 0;
	int ret = 0;
	int[][] map;
	int[] population;
	private void solution() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		ret = Integer.MAX_VALUE;
		N = Integer.parseInt(br.readLine());
		map = new int[N+1][N+1];
		population = new int[N+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1 ; i<=N ; i++) {
			population[i] = Integer.parseInt(st.nextToken());
		}
		for(int i=1 ; i<=N ; i++) {
			st = new StringTokenizer(br.readLine());
			int len = Integer.parseInt(st.nextToken());
			for(int j=0 ; j<len ; j++) {
				int city = Integer.parseInt(st.nextToken());
				map[i][city] = 1;
				map[city][i] = 1;
			}
		}
		boolean[] visited = new boolean[N+1];
		////////////////////////////////
		for(int i=1 ; i<=N/2 ; i++) {
			dfs(i,0,visited,0);
		}
		if(ret!=Integer.MAX_VALUE) {
			System.out.println(ret);
		}else {
			System.out.println(-1);
		}
		
	}
	private void dfs(int len, int dep,boolean[] visited,int befo) {
		if(dep==len) {
			List<Integer> region1 = new ArrayList<>();
			List<Integer> region2 = new ArrayList<>();
			for(int i=1 ; i<visited.length ; i++) {
				if(visited[i]) {
					region1.add(i);
				}else {
					region2.add(i);
				}
			}
//			System.out.println(region1+", "+region2);
			if(canGo(region1) && canGo(region2)) {
				int sum1 = getPopulation(region1);
				int sum2 = getPopulation(region2);
				int comp = Math.abs(sum1-sum2);
				ret = Math.min(comp, ret);
			}
			return;
		}
		for(int i=befo+1 ; i<visited.length ; i++) {
			if(!visited[i]) {
				visited[i] = true;
				dfs(len,dep+1,visited,i);
				visited[i] = false;
			}
		}
	}
	
	private boolean canGo(List<Integer> region) {
		boolean[] visited = new boolean[N+1];
		Queue<Integer> q = new LinkedList<>();
		q.offer(region.get(0));
		while(!q.isEmpty()) {
			int city = q.poll();
			if(region.contains(city) && !visited[city]) {
				visited[city] = true;
				for(int j=1 ; j<=N ; j++) {
					if(map[city][j]==1) {
						q.offer(j);
					}
				}
			}
		}
		for(int city : region) {
			if(!visited[city])
				return false;
		}
		return true;
	}
	
	private int getPopulation(List<Integer> region) {
		int sum = 0;
		for(int city : region) {
			sum += population[city];
		}
		return sum;
	}
}

📇 결과