[BOJ/Java] 17471. 게리맨더링

[BOJ/Java] 17471. 게리맨더링

17471번: 게리맨더링

---

문제 해석

이 문제는 N개의 구역을 두 그룹으로 나누어 각 그룹의 인구 차이를 최소화하는 문제이다. 각 구역의 인구수가 주어지고, 구역 간 연결 정보도 주어진다. 두 그룹은 각각 연결되어 있어야 하며(하나의 연결 요소를 이루어야 함), 불가능할 경우 -1을 출력한다.

풀이 과정

• 변수 선언 및 입력 처리: N은 구역의 수, num은 각 구역의 인구수를 저장하는 배열이다.
• 그래프 구성: 각 구역 간 연결 정보를 인접 리스트로 표현한 graph를 사용한다.
• 구역 나누기: sol 함수에서 구역을 나누는 모든 조합을 시도한다. combination 함수를 통해 가능한 모든 분할을 생성하고 검증한다.
• 연결성 검사: check 함수는 BFS를 사용해 주어진 구역 배열이 연결되어 있는지 확인한다.
• 인구 차이 계산: getDiff 함수로 두 그룹의 인구 차이를 계산한다.

코드

package edu.ssafy.im.BOJ.Gold.G4.No17471;

import java.io.*;
import java.util.*;

public class Main {
	private static int N;
	private static int[] num;
	private static ArrayList<ArrayList<Integer>> graph;
	private static int[] s;  // 한 그룹을 나타내는 배열
	private static int[] r;  // 다른 그룹을 나타내는 배열
	private static int ans = Integer.MAX_VALUE;  // 인구 차이의 최소값을 저장

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		num = new int[N];  // 구역의 인구 수

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

		graph = new ArrayList<>();
		for (int i = 0; i < N; i++)  // 각 구역의 연결 정보를 담는 그래프 초기화
			graph.add(new ArrayList<>());

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int E = Integer.parseInt(st.nextToken());
			for (int j = 0; j < E; j++) {
				int V = Integer.parseInt(st.nextToken()) - 1;
				graph.get(i).add(V);
			}
		}

		sol();
		sb.append(ans == Integer.MAX_VALUE ? -1 : ans);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private static void sol() {
		for (int i = 1; i <= N / 2; i++) {
			s = new int[i];
			r = new int[N - i];
			combination(0, 0);
		}
		ans = ans == Integer.MAX_VALUE ? -1 : ans;
	}
	
	private static boolean check(int[] a) {  // 주어진 구역이 연결되어 있는지 확인
		Queue<Integer> q = new ArrayDeque<>();
		int v = 1 << a[0];
		q.offer(a[0]);
		int cnt = 1;

		while (!q.isEmpty()) {
			int cur = q.poll();
			for (int i = 0; i < graph.get(cur).size(); i++) {
				int next = graph.get(cur).get(i);
				if(contains(a, next) && (v & (1 << next)) == 0) {
					q.offer(next);
					v |= 1 << next;
					cnt++;
				}
			}
		}

		return cnt == a.length;
	}

	private static boolean contains(int[] a, int next) {  // 배열 a에 next가 있는지 확인
		for (int v : a) if (v == next) return true;
		return false;
	}
	
	private static void combination(int k, int v) {  // 가능한 모든 구역 분할 조합 생성
		if (k == s.length) {
			makeR();
			if (check(s) && check(r)) ans = Math.min(ans, getDiff());
			return;
		}

		for (int i = 0; i < N; i++) {
			if ((v & (1 << i)) == 0) {
				s[k] = i;
				combination(k + 1, v |= 1 << i);
			}
		}
	}

	private static int getDiff() {  // 두 그룹의 인구 차이 계산
		int s1 = 0, s2 = 0;
		for (int val : s) s1 += num[val];
		for (int val : r) s2 += num[val];
		return Math.abs(s1 - s2);
	}

	private static void makeR() {  // 한 그룹이 정해지면 다른 그룹 자동 생성
		int idx = 0;
		for (int i = 0; i < N; i++) {
			boolean f = false;
			for (int j : s) {
				if (i == j) {
					f = true;
					break;
				}
			}
			if (!f)
				r[idx++] = i;
		}
	}
}

시간 복잡도 분석

• 이 문제의 해결을 위해 가능한 모든 그룹 분할 조합을 생성하고 각 조합에 대해 검증한다. 이로 인한 시간 복잡도는 𝑂(2^𝑁)이 될 수 있다.

느낀점

게리맨더링 문제는 그래프 이론과 조합론을 결합하여 해결해야 하는 복잡한 문제다. 특히 모든 가능한 경우의 수를 고려해야 하며, 각 경우에서 두 그룹이 모두 연결되어 있어야 한다는 추가적인 조건을 만족시켜야 한다. 이 문제를 통해 복잡한 조건을 만족하는 최적의 해를 찾는 알고리즘 설계에 대한 이해를 높일 수 있었다.