[백준] 17471번 - 게리맨더링 풀이 및 코드 분석 (Java)

문제 링크

1. 문제 분석

🏙️ 문제 개요

백준시의 시장이 공정한 선거를 위해 도시를 두 개의 선거구로 나누려고 한다. 각 선거구는 최소 한 개의 구역을 포함해야 하며, 모두 연결된 형태여야 한다.
이때, 두 선거구의 인구 차이를 최소화하는 방법을 찾는 것이 목표다.

🎯 요구사항

1. 두 개의 선거구로 구분해야 한다.
2. 각 선거구 내 구역들이 연결되어 있어야 한다.
3. 두 선거구의 인구 차이의 최솟값을 구해야 한다.
4. 선거구를 나누는 것이 불가능한 경우 -1을 출력해야 한다.

---

2. 해결 방법

🔹 핵심 개념

이 문제는 브루트포스(모든 경우 탐색) + 그래프 탐색(BFS) 방식으로 해결할 수 있다.

1. 구역을 두 선거구로 나누는 모든 경우의 수를 생성
   • N개의 구역을 두 개의 그룹으로 나누는 모든 조합을 찾는다.
   • 선거구의 크기는 최소 1개 이상이므로, 첫 번째 선거구의 크기를 1부터 N-1까지로 설정해 조합을 구한다.
2. 각 그룹이 연결된 형태인지 검사
   • BFS 탐색을 활용하여 각 선거구가 연결되어 있는지 확인한다.
3. 각 선거구의 인구 차이를 계산하여 최솟값을 갱신
   • 연결된 경우, 두 선거구의 인구 차이를 계산하고 최소값을 업데이트한다.

---

3. 코드 구현

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

public class Main {
    static int N, minDiff = Integer.MAX_VALUE;
    static int[] population;
    static List<Integer>[] graph;

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

        population = new int[N + 1];
        graph = new ArrayList[N + 1];

        // 인구 정보 입력
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            population[i] = Integer.parseInt(st.nextToken());
            graph[i] = new ArrayList<>();
        }

        // 인접 구역 정보 입력
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int count = Integer.parseInt(st.nextToken());
            for (int j = 0; j < count; j++) {
                int neighbor = Integer.parseInt(st.nextToken());
                graph[i].add(neighbor);
            }
        }

        // 구역을 두 개의 선거구로 나누는 모든 조합 확인
        for (int size = 1; size <= N / 2; size++) {
            generateCombinations(new ArrayList<>(), 1, size);
        }

        // 결과 출력
        System.out.println(minDiff == Integer.MAX_VALUE ? -1 : minDiff);
    }

    // 부분 집합(선거구) 조합 생성
    static void generateCombinations(List<Integer> districtA, int start, int size) {
        if (districtA.size() == size) {
            checkAndUpdate(districtA);
            return;
        }

        for (int i = start; i <= N; i++) {
            districtA.add(i);
            generateCombinations(districtA, i + 1, size);
            districtA.remove(districtA.size() - 1);
        }
    }

    // 두 선거구가 연결되어 있는지 확인하고 인구 차이 갱신
    static void checkAndUpdate(List<Integer> districtA) {
        boolean[] isInA = new boolean[N + 1];
        for (int node : districtA) isInA[node] = true;

        List<Integer> districtB = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            if (!isInA[i]) districtB.add(i);
        }

        if (districtB.isEmpty()) return; // 둘 중 하나가 비어있는 경우 제외

        if (isConnected(districtA, isInA) && isConnected(districtB, isInA)) {
            int sumA = districtA.stream().mapToInt(i -> population[i]).sum();
            int sumB = districtB.stream().mapToInt(i -> population[i]).sum();
            minDiff = Math.min(minDiff, Math.abs(sumA - sumB));
        }
    }

    // BFS를 사용한 연결성 검사
    static boolean isConnected(List<Integer> district, boolean[] isInA) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];
        queue.add(district.get(0));
        visited[district.get(0)] = true;
        int count = 1;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : graph[node]) {
                if (!visited[neighbor] && (isInA[node] == isInA[neighbor])) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                    count++;
                }
            }
        }

        return count == district.size();
    }
}

---

4. 코드 분석

🔹 주요 알고리즘

1. 부분집합 생성 (조합)
   • generateCombinations 함수에서 크기 1부터 N/2까지의 모든 선거구 A 조합을 생성한다.
   • A에 속하지 않은 구역들은 자동으로 선거구 B가 된다.
2. 연결성 검사 (BFS)
   • isConnected 함수에서 BFS를 활용해 두 선거구가 각각 연결되어 있는지 확인한다.
3. 인구 차이 계산 및 최솟값 갱신
   • 두 선거구의 인구 합을 계산한 후, 최소 인구 차이를 업데이트한다.

🔹 시간 복잡도 분석

• generateCombinations는 약 2^N번 호출됨. (브루트포스)
• 각 조합마다 BFS 두 번 수행 (최대 O(N))
• 최악의 경우 (2^10) * (10) = 10,240번 연산으로, N ≤ 10일 때 충분히 실행 가능.

---

5. 개선할 점 및 대체 방법

✅ 개선할 점

1. DFS를 사용한 연결성 검사
   • BFS 대신 DFS로 변경하여 코드 단순화 가능
2. 비트마스킹 활용
   • N이 작으므로 비트마스킹(비트 필터링)을 활용하면 조합 생성을 더 빠르게 처리 가능
3. 조합을 생성할 때 연결성을 미리 확인
   • A 선거구를 구성할 때 이미 연결된 그룹인지 체크하면 불필요한 연산을 줄일 수 있음

🔄 대체 방법

1. Union-Find 활용
   • 연결성 검사를 Union-Find(서로소 집합)로 구현하면 성능 최적화 가능
2. Bitmask & DP 적용
   • 1 << N을 활용해 조합을 생성하면 연산량을 줄일 수 있음