[백준] 17471 게리멘더링

1. 문제

2. 접근방법

부분집합으로 가능한 첫번째 선거구를 구하고 골라지지 않은 다른 지역들을 두번째 선거구로 뽑은다음

각 선거구들이 모두 이어져있는지 검사한 뒤

둘 다 잘 이어져 있다면 각 선거구의 인원 합의 차를 구해 최솟값을 구하는 문제

 

이 문제도 할것이 굉장히 많다.

 

우선 부분집합을 비트마스킹을 활용해 구하였다. (부분집합을 비트마스크로 뽑는 것은 구글링 ㄱㄱ)

비트 마스킹을 사용하면 (모든구역 - 뽑힌 비트마스크)를 하면 쉽게 두번째 선거구 역시 구할 수 있다.

이 상황을 비트마스크로 표현하면

첫번째 뽑은 선거구

001101

 

전체 선거구

-첫번째 뽑은 선거구

-----------------------

= 두번째 뽑은 선거구

 

 111111

-001101

-------------

110010

 

그리고 뽑을 때

123 뽑고 456 뽑으나

456 뽑고 123 뽑으나 같으니

 

부분집합을 절반까지만 뽑으면 된다.

 

 

이 후 뽑힌 두 비트마스크를 bfs로 다 연결 되어있는지 검사하고

두 선거구의 인원들의 차를 구하면 되겠다.

 
3. 풀이

1. 입력을 인접행렬로 받아오기 (인접리스트도 괜찮다)

2. 비트마스크를 1부터 ((1 << N) - 1)/2  까지 1씩 증가하며 뽑기 //하나도 안뽑히는 경우는 없다고 하였으므로

3. ((1 << N)-1 - 첫번째선거구비트)로 두번째 선거구 뽑기

4. bfs돌며 각 선거구 다 이어졌는지 검사

5. 둘다 이어져 있으면 인원수 구하고 인원수의 차이를 구하기

6. min보다 작으면 min에 저장

4. 자바 코드

package Gold;

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

public class P17471게리멘더링 {
	static int people[];
	static int N;
	static boolean matrix[][];
	static int min = 123456789;
	public static void main(String[] args) throws IOException {
		// 모든 부분 집합을 비트마스크로 뽑는다.
		// 모든구역 - 뽑은 비트마스크 하면 반대편 선거구도 뽑힌다.
		// 두 구역 모두 연결 되어있는지 bfs검사
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		people = new int[N + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++)
			people[i] = Integer.parseInt(st.nextToken());

		matrix = new boolean[N + 1][N + 1];
		for (int i = 1; i <= N; i++) { //입력 받기
			st = new StringTokenizer(br.readLine());
			int etc = Integer.parseInt(st.nextToken());
			for (int j = 0; j < etc; j++) {
				int target = Integer.parseInt(st.nextToken());
				matrix[i][target] = true;
				matrix[target][i] = true;
			}
		}

		for (int i = 1; i <= ((1 << N) - 1) / 2; i++) {
			ArrayList<Integer> section_1 = makeSection(i);
			if (!check(section_1))
				continue;
				
			
			ArrayList<Integer> section_2 = makeSection((1 << N)-1 - i);
			if (!check(section_2))
				continue;
			
			int diff = Math.abs(getPeople(section_1) - getPeople(section_2));
			min = Math.min(diff, min);
		}
		if(min == 123456789)
			min = -1;
		System.out.println(min);

	}

	static ArrayList<Integer> makeSection(int Section) {
		ArrayList<Integer> section = new ArrayList<Integer>();
		for (int i = 0; i < N; i++) {
			if ((Section & (1 << i)) != 0)
				section.add(i+1);
		}
		return section;
	}
	static boolean check(ArrayList<Integer> originSection) {
		ArrayList<Integer> section = (ArrayList<Integer>) originSection.clone(); 
		Queue<Integer> que = new LinkedList<Integer>();
		que.offer(section.get(0));
		section.remove(0);
		while (!que.isEmpty()) {
			int now = que.poll();
			for (int i = section.size() - 1; i >= 0; i--) {
				if (matrix[now][section.get(i)]) {
					que.offer(section.get(i));
					section.remove(i);
				}
			}
		}
		if(section.size() == 0)
			return true;
		return false;
	}

	static int getPeople(ArrayList<Integer> section) {
		int sum = 0;
		for(int i : section)
			sum += people[i];
		return sum;
	}
}

5. 마치며

이 문제가 삼성 A형 기출이라던데

기본 개념들은 어렵지 않으나 여러 개념이 섞여 있어 체력 기르기에 좋은 문제였다.