[백준] 17471번 : 게리맨더링 - 자바(JAVA)

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

17471번: 게리맨더링

 

문제 해석

N개의 구역이 존재하고 이 구역은 1번부터 N번까지 번호가 매겨져 있습니다.

구역을 두 개의 선고 구로 나누어야 하고, 각 구격은 두 선거구 중 하나에 포함되어야 합니다.

선거구는 구역을 적어도 하나 포함해야 하며, 한 선거구에 속한다면 모두 연결되어 있어야 합니다.

구역 A에서 B로 이동할 수 있다면 이는 연결되어 있다고 할 수 있습니다.

공평하게 선거구를 나누기 위해 두 선거구에 포함된 인구의 차이를 최소로 하려고 합니다.

백준 시의 정보가 주어졌을 때 인구 차이의 최솟값을 구해봅시다.

 

문제 풀이 전 설계

시간제한 : 0.5초

N의 범위가 2~10으로 아주 작다.

 

1개의 선거구에 대해 구역에 1개일 때, 2개일 때, 3개일 때... N개일 때로 나누어 nC1, nC2, nC3,... nCn을 통해 선거구 조합을 구합니다.

 

그러면 자동적으로 남은 선거구를 구할 수 있게 되는데 선거구들은 각각 연결되어있어야 합니다.

연결되지 않은 선거구가 존재하면 진행하지 않고 만약 두 선거구들이 연결되어 있다면 인원수를 비교하여 인구 차이의 최솟값을 갱신해 나갑니다.

 

문제 풀이 하면서

부분집합을 구할 때 절반까지만 구하면 됩니다.

왜냐하면 6C1 = 6C5, 6C2 = 6C4는 같기 때문입니다.

 

이후 조합을 통해 얻은 선거구 1, 선거구 2가 연결되었는지 확인하고

연결되었다면 비교하여 최솟값을 갱신하는 로직은 동일합니다.

 

연결됨을 비교할 때는 BFS를 사용합니다.

또한 연결됨을 비교할때는 인접 리스트를 사용하는데 이때 현재 선거구에 포함되어있는지까지 검사해주어야 합니다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Position {
    int x;
    int peopleNum;
 
    Position(int x, int peopleNum) {
        this.x = x;
        this.peopleNum = peopleNum;
    }
}
 
public class Main_17471_게리맨더링 {
    static int N;
    static Position[] positions; // 지역의 번호와 인구수를 담은 객체 배열.
    static ArrayList<ArrayList<Integer>> list; // 연결리스트
    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));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
 
        positions = new Position[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            int peopleNum = Integer.parseInt(st.nextToken());
            positions[i] = new Position(i, peopleNum);
        }
 
        list = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            for (int j = 0; j < n; j++) {
                int temp = Integer.parseInt(st.nextToken());
                list.get(i).add(temp);
            }
        }
        //////////// 입력 끝.
 
        ArrayList<Integer> A = new ArrayList<>();
        for (int i = 1; i <= N / 2; i++) {
            comb(1, N, i, A); // 조합을 통한 지역 분리.
        }
 
        // ans가 초기값 그대로라면, 게리멘더링에 실패한 것임.
        if (ans == Integer.MAX_VALUE) {
            ans = -1;
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
    // 조합
    public static void comb(int start, int n, int r, ArrayList<Integer> A) {
        if (r == 0) {
            gerrymandering(A);
            return;
        }
 
        for (int i = start; i <= n; i++) {
            A.add(i);
            comb(i + 1, n, r - 1, A);
            A.remove(A.size() - 1);
        }
    }
 
    // 할당받은 지역의 인구수의 차이를 계산하는 함수.
    public static void gerrymandering(ArrayList<Integer> A) {
        // A 지역구가 잘 연결되어있는지 확인
        if(!isConnect(positions[A.get(0)].x, A, A.size())) {
            return;
        }
 
        ArrayList<Integer> B = new ArrayList<>();
        for (int i = 1; i <= N; i++) {
            if (A.contains(i)) {
                continue;
            }
            B.add(i);
        }
        
        // B 지역구가 잘 연결되어있는지 확인
        if(!isConnect(positions[B.get(0)].x, B, B.size())) {
            return;
        }
 
        int resultA = 0;
        
        // A 지역구 인구 계산
        for (int i = 0; i < A.size(); i++) {
            resultA += positions[A.get(i)].peopleNum;
        }
 
        int resultB = 0;
        
        // B 지역구 인구 계산
        for (int i = 0; i < B.size(); i++) {
            resultB += positions[B.get(i)].peopleNum;
        }
 
        int result = Math.abs(resultA - resultB);
        ans = Math.min(ans, result);
 
    }
    
    // 선거구가 모두 연결되어있는지 확인.
    public static boolean isConnect(int num, ArrayList<Integer> arr, int size) {
        boolean[] visited = new boolean[N + 1];
        visited[num] = true;
        Queue<Integer> q = new LinkedList<>();
        q.offer(num);
 
        int count = 1;
        while (!q.isEmpty()) {
            int start = q.poll();
 
            for (int i : list.get(start)) {
                // 이미 방문한 적이 없고, arr에 속해야 함.
                if (!visited[i] && arr.contains(i)) {
                    visited[i] = true;
                    count++;
                    q.offer(i);
                }
            }
        }
 
        if (count == size) {
            return true;
        }
        return false;
    }
 
}

 

출처

https://steady-coding.tistory.com/33

[BOJ] 백준 17471번 : 게리멘더링 (JAVA)