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

문제

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

 

어떻게 풀 것인가?

문제의 접근조차 어려워서 잠깐의 고민 끝에 결국엔 다른분의 풀이를 참고하였다. 오늘의 포스팅은 기억을 남기기 위한 용도라고 생각하며 작성하였다.

 

문제의 접근의 경우 

1. 지역에 두 개의 선거구 중에 하나를 할당한다. (1 또는 2로 표현)
2. 나눠진 지역들이 두개의 구역으로 연결되는지 확인한다. (DFS/BFS 탐색으로 구함)
3. 두 지역의 차이 값 중에서 최소값을 찾아준다.

좀 더 풀어서 작성해보자.

 

먼저, 입력을 통해 각 지역의 인구 수와 연결된 지역 정보를 받아 저장한다. 이후, 선거구를 나누기 위해 각 지역이 속할 선거구를 정하는 모든 경우의 수를 탐색한다. 이를 위해 깊이 우선 탐색(DFS)을 사용하며, 각 지역을 두 개의 선거구 중 하나에 할당한다.

모든 지역에 대한 선거구 할당이 완료되면, 두 선거구가 각각 내부적으로 연결되어 있는지 확인한다. 연결 여부를 판별하기 위해 너비 우선 탐색(BFS)을 활용하며, 방문 여부를 체크하여 분리된 영역이 없는지 검사한다.

만약 두 선거구가 내부적으로 연결되어 있다면, 해당 구성을 통해 인구 차이를 계산하고 최소값을 갱신한다. 이러한 과정을 모든 가능한 경우에 대해 수행한 후, 최소 인구 차이를 출력한다. 만약 두 개의 유효한 선거구를 만들 수 없다면 -1을 출력한다.

 

풀면서 놓쳤던점

문제의 접근조차 어려웠다. 구현, DFS, BFS를 모두 불어보는 문제였다.

 

이 문제를 통해 얻어갈 것

구현능력 + 완전탐색 + DFS/BFS 개념을 모두 활용해 볼 수 있는 문제

 

내 코드 

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;
				}
			}
		}
	}
}

 

참고

https://moonsbeen.tistory.com/254

[백준]17417: 게리맨더링 - JAVA