[BaekJoon] 17471번 게리맨더링 (Java) 문제 풀이 [Gold 3]

문제

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

 

어떻게 풀 것인가?

 

N개의 구역(1~N)으로 이루어진 도시에서, 각 구역의 인구와 인접 정보가 주어진다.

이 도시를 두 선거구로 나눠야 한다.

 

• 각 선거구는 적어도 1개의 구역을 가져야 함.
• 각 선거구 내부는 반드시 서로 연결되어야 함(같은 선거구끼리 인접해서 이동 가능).

두 선거구의 인구 차이의 최솟값을 구하는 문제이다. 두 선거구로 나눌 수 없으면 -1을 출력

 

문제를 자세히 보자. 일단 N <= 10이므로 모든 경우의 수(부분 집합)을 통해서 다 따져볼 수 있다.

 

• 각 구역을 1번/2번 선거구 중 하나에 모든 조합으로 나누어 본다(총 2^N가지).
• 나눠진 두 집합이 각각 내부적으로 연결되어 있는지 확인한다.
• 조건을 만족하면 두 선거구의 인구 합의 차이를 구해서 최솟값을 갱신한다.

 

 

 

이 문제의 핵심은 부분집합이다.

부분 집합의 개념은 아래를 참고해보자.

https://superohinsung.tistory.com/386

[Algorithm] 부분집합에 대해서 with Java

 

 

• dfs(int k)
  • k번째 구역부터 1 or 2 선거구로 배정하여 모든 경우의 수를 만든다.
  • N+1번째 구역까지 배정이 끝나면,
    • 두 선거구가 각각 연결되어 있는지 체크
    • 둘 다 연결되어 있으면 인구 차이 갱신
• bfs(int idx, int areaNum)
  • idx 구역을 시작점으로, areaNum 선거구에 포함된 구역들을 BFS로 모두 방문한다.
  • visited[] 배열로 방문 체크.
• 연결성 판단
  • visited[]를 돌며 아직 방문 안한 구역이 있으면, 그 구역부터 BFS
  • 두 번만 BFS가 돌아야 2개의 연결된 선거구가 만들어진 것

 

 

내 코드 

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 Main {

	static int N;
	static int[] population, area;
	static ArrayList<Integer>[] list;
	static int min = Integer.MAX_VALUE;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());

		population = new int[N + 1];
		list = new ArrayList[N + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			list[i] = new ArrayList<>();
			population[i] = Integer.parseInt(st.nextToken());
		}

		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			int num = Integer.parseInt(st.nextToken());
			for (int j = 0; j < num; j++) {
				list[i].add(Integer.parseInt(st.nextToken()));
			}
		}

		area = new int[N + 1]; // 각 지역구가 속한 선거구 저장. 1 또는 2
		dfs(1); // 뽑을 수 있는 모든 지역구를 뽑는 dfs탐색

		if (min == Integer.MAX_VALUE)
			System.out.println("-1");
		else
			System.out.println(min);
	}

	public static void dfs(int k) {
		if (k == N + 1) { // 모든 지역 다 뽑았다면
			int area1 = 0;
			int area2 = 0;
			for (int i = 1; i <= N; i++) {
				if (area[i] == 1)
					area1 += population[i];
				else
					area2 += population[i];
			}

			visited = new boolean[N + 1];
			int link = 0; // 연결된 지역들의 개수를 셈.
			for (int i = 1; i <= N; i++) {
				if (!visited[i]) {
					bfs(i, area[i]); // 연결된 지역들을 모두 방문표시하는 bfs탐색
					link++;
				}
			}
			// 지역이 2개뤄 나눠졌고, 2지역안에서 서로 연결되어 있다면 최소값 계산
			if (link == 2)
				min = Math.min(min, Math.abs(area1 - area2));

			return;
		}

		area[k] = 1; // k지역 1번 선거구에 할당.
		dfs(k + 1);

		area[k] = 2; // k지역 2번 선거구에 할당.
		dfs(k + 1);
	}

	public static void bfs(int idx, int areaNum) {
		Queue<Integer> queue = new LinkedList<>();
		visited[idx] = true;
		queue.offer(idx);

		while (!queue.isEmpty()) {
			int current = queue.poll();

			for (int i = 0; i < list[current].size(); i++) {
				int next = list[current].get(i);
				if (area[next] == areaNum && !visited[next]) {
					queue.offer(next);
					visited[next] = true;
				}
			}
		}
	}
}