[백준] 17471. 게리맨더링 - Java

🖇️ 문제 링크

17471번: 게리맨더링

문제 백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다.

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

 

---

💡 문제 분석

1. 각 구역을 두 개의 선거구로 나눕니다. 총 N개의 구역이 있다면, (1, N - 1), (2, N - 2) ... (N/ 2, N/2) 형태로 나눕니다.

 

2. 두 개로 나눈 선거구가 각각 연결되어 있는지 그래프 탐색으로 확인합니다.

 

3. 만약 연결되어 있다면 인구수의 차이의 최솟값을 구합니다.

 

 

---

⌨️ 코드

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

public class Q17471 {
    static int N, ret = Integer.MAX_VALUE;
    static int[] people;
    static boolean[] chk;
    static ArrayList<Integer>[] adj;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        adj = new ArrayList[N];
        people = new int[N];
        chk = new boolean[N];

        for(int i = 0; i < N; i++) {
            people[i] = sc.nextInt();
            adj[i] = new ArrayList<>();
        }

        for(int i = 0; i < N; i++) {
            int s = sc.nextInt();
            for(int j = 0; j < s; j++)
                adj[i].add(sc.nextInt() - 1);
        }

        for(int i = 1; i <= N / 2; i++) {
            Arrays.fill(chk, false);
            comb(i, 0, 0);
        }

        System.out.println((ret == Integer.MAX_VALUE) ? -1 : ret);
    }

    static void comb(int num, int idx, int cnt) {
        if(idx >= N) return;
        if(cnt == num) {
            if(isConnect())
                ret = Math.min(ret, count());
            return;
        }

        chk[idx] = true;
        comb(num, idx + 1, cnt + 1);
        chk[idx] = false;
        comb(num, idx + 1, cnt);
    }

    static boolean isConnect() {
        ArrayList<Integer> pick1 = new ArrayList<>();
        ArrayList<Integer> pick2 = new ArrayList<>();
        for(int i = 0; i < N; i++)
            if(chk[i]) pick1.add(i);
            else pick2.add(i);
        return bfs(pick1.get(0), pick1, true) && bfs(pick2.get(0), pick2, false);
    }

    static boolean bfs(int n, ArrayList<Integer> list, boolean check) {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[N];
        q.add(n);
        visited[n] = true;
        while(!q.isEmpty()) {
            int cur = q.poll();
            for(int next : adj[cur]) {
                if(visited[next] || chk[next] != check) continue;
                visited[next] = true;
                q.add(next);
            }
        }

        for(int num : list)
            if(!visited[num]) return false;

        return true;
    }

    static int count() {
        int sum = 0;
        for(int i = 0; i < N; i++)
            if(chk[i]) sum += people[i];
            else sum -= people[i];
        return Math.abs(sum);
    }
}

 

---

⏱️ 결과

 

 

 

Uploaded by Notion2Tistory v1.1.0