[백준 / BOJ] 17471 게리맨더링

문제

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

17471번: 게리맨더링

N개의 선거구와 각 선거구에 사는 인원수가 주어진다.

 

선거구는 2개의 선거진영으로 나뉘며, 이때, 각 선거진영 선거진영 별로 모두 연결되어있어야한다.

 

이때, 선거진영의 인구수 차이를 최소화하는 값을 구하는 문제다.

---

풀이

비트마스킹을 이용한 완전탐색으로 푼 문제다.

처음엔 비트마스킹 + 백 트래킹으로 생각했으나, 이 방법으로는 모든 경우를 봐주지 못해서 풀기 힘들어 보였다. 

 

알고리즘은 다음과 같다.

 

1. 만들 수 있는 모든 조합을 만든다. 이때, 조합은 선거구 i 를 자신의 선거지역으로 만드느냐 아니냐가 되므로, 2^10이 나온다.

	private int getMinimumDif(int idx, int field, int num){
		if(idx > N && checkConnection(field)) return abs((totalNum - num) - num);
		if(idx > N) return 987654321;
		return Math.min(
			getMinimumDif(idx+1, field | (1 << idx), num + peo[idx])
			, getMinimumDif(idx+1, field, num)
		);
	}

 

2. 조합이 완성 되었을때, 선거진영이 서로 연결되어 있는지 확인한다.

	private boolean checkConnection(int field){
		int[] visit = new int[N+2];
		boolean visitA = false, visitB = false;
		for(int i = 0; i <= N; i++) visit[i] = -1;
		for(int i = 1; i <= N; i++){
			if((field & (1 << i)) > 0){
				markVisit(i, 1, visit, field);
				visitA = true;
				break;
			}
		}
		for(int i = 1; i <= N; i++){
			if((field & (1 << i)) == 0){
				markVisit(i, 0, visit, field);
				visitB = true;
				break;
			}
		}
		if(!visitA || !visitB) return false;
		for(int j = 1; j <= N; j++) if(visit[j] == -1) return false;
		return true;
	}
	
	private void markVisit(int idx, int num, int[] visit, int field){
		visit[idx] = num;
		for(int i = 1; i < node.get(idx).size(); i++){
			int nextIdx = node.get(idx).get(i);
			if(visit[nextIdx] != -1) continue;
			if(num == 0 && (field & (1 << nextIdx)) > 0) continue;
			if(num > 0 && (field & (1 << nextIdx)) == 0) continue;
			markVisit(nextIdx, num, visit, field);
		}
	}

 

인자로 비트를 넘겨주는것을 유심히 살펴보자. 비트 변수명은 모두 field이다.

N개의 선택지가 있고, 매 선택지마다 선택하느냐 안하느냐로 나뉘므로, 시간복잡도는 O(2^N)이 된다.

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/17471%20%EA%B2%8C%EB%A6%AC%EB%A7%A8%EB%8D%94%EB%A7%81/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃