[백준] JAVA - 17471. 게리맨더링

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

17471번: 게리맨더링

 

생각

선거구를 두 그룹으로 나누고 나눈 그룹들은 해당 그룹 내부에서 서로 연결되어 있어야 합니다.

 

문제 풀이의 큰 흐름은 다음과 같습니다.

- 두 그룹으로 나누는 모든 경우를 구한다. 
- 나눈 두 그룹이 각각 내부에서 서로 연결되어있는지 확인한다. 
- 두 그룹이 해당 그룹 내부에서 모두 서로 연결되어있다면 두 그룹의 인구 수 차이를 계산한다.

 

1. 두 그룹으로 나누는것은 재귀함수를 사용했습니다. 1 ~ N/2개가 될때까지 하나의 그룹(A그룹) 을 만들어주고 A그룹에 속해있지 않은 마을들은 B그룹에 속합니다. (for문을 사용하여 비트마스킹으로 두 그룹으로 나눌수도 있네요!)

 

2. A그룹과 B그룹이 각각 해당 그룹 내부에서 서로 연결되있음을 판단하는 함수 isConnect를 만들었습니다.

먼저 group의 크기가 1이면 선거구의 크기가 1인것이므로 바로 true를 리턴합니다.

그 다음으로, BFS를 사용하여 연결성을 체크하는데 다음 노드에 갈수있는지를 판단하는 기준은 방문여부와 내가 나눈 그룹에 속해있는지를 판단해야하는 두가지를 모두 체크해야합니다.

마지막으로 나눈 그룹의 사이즈와 내가 방문한 사이즈가 동일한지도 추가적으로 확인해줬습니다.

 

3. A그룹과 B그룹이 해당 그룹 내부에서 모두 서로 연결되어있다면 두 그룹의 인구 수 차이를 계산합니다.

 

4. 그룹을 아예 나누지못할때가 존재하므로 ans의 초기값이 Integer.MAX_VALUE와 동일하다면 -1을 리턴해주고 그렇지 않다면 찾아준 최소값을 출력합니다

 

Java Code

package com.java.algorithm;

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 BOJ_17471_게리맨더링 {
	static int N;
	static int[] people;
	static int[] areaA;
	static int[] areaB;
	static boolean[] isSelected;
	static List<Integer>[] adjList;
	static int ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		people = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			people[i] = Integer.parseInt(st.nextToken());
		}
		
		adjList = new ArrayList[N+1];
		for (int i = 0; i <= N; i++) {
			adjList[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int adjCnt = Integer.parseInt(st.nextToken());
			for (int j = 0; j < adjCnt; j++) {
				adjList[i+1].add(Integer.parseInt(st.nextToken()));
			}
		}
		ans = Integer.MAX_VALUE;
		//1 ~ n/2개로 나누기
		for (int i = 1; i <= N/2; i++) {
			areaA = new int[i];
			areaB = new int[N-i];
			solve(0, 0, i);
		}
		ans = ans == Integer.MAX_VALUE ? -1 : ans;
		System.out.println(ans);
		
	}
	// 그룹나눠줌 
    // 각각 내부에서 연결되있는지 체크
    // 차이값 계산
	private static void solve(int cnt, int start, int total) {
		if(cnt == total) {
			isSelected = new boolean[N];
			List<Integer> groupA = new ArrayList<>();
			List<Integer> groupB = new ArrayList<>();
			
			for (int i = 0; i < areaA.length; i++) {
				isSelected[areaA[i]] = true;
			}
			
			for (int i = 0; i < N; i++) {
				if(!isSelected[i]) {
					groupB.add(i+1);
				}else {
					groupA.add(i+1);
				}
			}
			
			//두 그룹 각각 내부에서 연결되어있는지 체크
			if(isConnect(groupA) && isConnect(groupB)) {
				
				//인구 수 차이 계산
				ans = Math.min(ans, diffCount(groupA, groupB));
			}
			
			return;
		}
		for (int i = start; i < N; i++) {
			areaA[cnt] = i;
			solve(cnt+1, i+1, total);
		}
	}

	private static int diffCount(List<Integer> groupA, List<Integer> groupB) {
		int sumA=0, sumB=0;
		for (int i = 0; i < groupA.size(); i++) {
			sumA+=people[groupA.get(i)-1];
		}
		for (int i = 0; i < groupB.size(); i++) {
			sumB+=people[groupB.get(i)-1];
		}
		return Math.abs(sumA-sumB);
	}
	
	private static boolean isConnect(List<Integer> group) {
		if(group.size() == 1) return true;
		
		Queue<Integer> q = new LinkedList<>();
		boolean[] visited = new boolean[N+1];
		//group : 2 5 6
		q.add(group.get(0));
		visited[group.get(0)]= true;
		
		while(!q.isEmpty()) {
			int size = q.size();
			while(size-- > 0) {
				int now = q.poll();
				for (int i = 0; i < adjList[now].size(); i++) {
					int next = adjList[now].get(i);
					
					if(!visited[next] && isNext(next, group)) {
						visited[next] = true;
						q.add(next);
					}
				}
			}
		}

		//vistied 조사
		int visitCnt = 0;
		for (int i = 0; i <= N; i++) {
			if(visited[i]) visitCnt++;
		}
		return visitCnt == group.size() ? true : false;
	}
	
	//다음 방문 노드가 group에 있는 원소인지 확인
	private static boolean isNext(int next, List<Integer> group) {
		boolean flag = false;
		for (int i = 0; i < group.size(); i++) {
			if(group.get(i) == next) {
				flag = true;
			}
		}
		return flag;
	}

}

 

Java Code2 - 비트마스킹으로 부분집합 구하기

package com.java.algorithm;

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 BOJ_17471_게리맨더링 {
	static int N;
	static int[] people;
	static int[] areaA;
	static int[] areaB;
	static boolean[] isSelected;
	static List<Integer>[] adjList;
	static int ans;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		people = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			people[i] = Integer.parseInt(st.nextToken());
		}
		
		adjList = new ArrayList[N+1];
		for (int i = 0; i <= N; i++) {
			adjList[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int adjCnt = Integer.parseInt(st.nextToken());
			for (int j = 0; j < adjCnt; j++) {
				adjList[i+1].add(Integer.parseInt(st.nextToken()));
			}
		}
		ans = Integer.MAX_VALUE;
		solve(1<<N);
		ans = ans == Integer.MAX_VALUE ? -1 : ans;
		System.out.println(ans);
		
	}
	
	private static void solve(int Nbit) {
		List<Integer> groupA = new ArrayList<Integer>();
		List<Integer> groupB = new ArrayList<Integer>();
		for (int i = 0; i < Nbit; i++) {
			for (int j = 0; j < N; j++) {
				if((i & (1<<j)) > 0) groupA.add(j+1);
				else {
					groupB.add(j+1);
				}
			}
			
			if(groupA.size() > 0 && groupB.size() > 0) {
				//나눈 그룹들 각각 내부에서 연결되있는지 체크
				if(isConnect(groupA) && isConnect(groupB)) {
					ans = Math.min(ans, diffCount(groupA, groupB));
				}
			}

			groupA.clear();
			groupB.clear();
		}
		
	}

	private static int diffCount(List<Integer> groupA, List<Integer> groupB) {
		int sumA=0, sumB=0;
		for (int i = 0; i < groupA.size(); i++) {
			sumA+=people[groupA.get(i)-1];
		}
		for (int i = 0; i < groupB.size(); i++) {
			sumB+=people[groupB.get(i)-1];
		}
		return Math.abs(sumA-sumB);
	}
	
	private static boolean isConnect(List<Integer> group) {
		if(group.size() == 1) return true;
		
		Queue<Integer> q = new LinkedList<>();
		boolean[] visited = new boolean[N+1];

		q.add(group.get(0));
		visited[group.get(0)]= true;
		
		while(!q.isEmpty()) {
			int size = q.size();
			while(size-- > 0) {
				int now = q.poll();
				for (int i = 0; i < adjList[now].size(); i++) {
					int next = adjList[now].get(i);
					
					if(!visited[next] && isNext(next, group)) {
						visited[next] = true;
						q.add(next);
					}
				}
			}
		}

		//vistied 조사
		int visitCnt = 0;
		for (int i = 0; i <= N; i++) {
			if(visited[i]) visitCnt++;
		}
		return visitCnt == group.size() ? true : false;
	}
	
	//다음 방문 노드가 group에 있는 원소인지 확인
	private static boolean isNext(int next, List<Integer> group) {
		boolean flag = false;
		for (int i = 0; i < group.size(); i++) {
			if(group.get(i) == next) {
				flag = true;
			}
		}
		return flag;
	}


}