[BOJ] 백준 17471 게리맨더링 (JAVA)

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

17471번: 게리맨더링

 

🔍 Solve

조합을 이용한 완전 탐색이며, dfs를 사용했습니다.

다음과 같은 순서로 구현했습니다.

1. 그래프(배열) 만들기 - 조합

2. 선거구 연결 - 그래프 탐색(dfs)

3. 인구수 파악

 

부분집합이 아닌 조합을 사용한 이유는, 배열 1이 뽑혔으면 배열 2는 배열 1의 여집합이기 때문에 부분 조합을 사용하면 중복되는 배열이 반환됩니다. 따라서 1부터 N/2까지의 개수를 뽑는 조합을 사용했습니다.

조합 코드에서 true인 그룹을 먼저 탐색하고, false인 그룹을 동일하게 탐색합니다.

 

true인 그룹을 대표적으로 살펴보면, dfs를 탐색할 때 처음 시작하는 위치가 필요하므로, getStart함수를 사용하여 제일 먼저 만나는 true의 인덱스를 찾아주었습니다. 해당 인덱스부터 dfs를 돌며 연결되어있는 구역의 인구수를 더해줍니다. 연결되어있는 구역의 개수를 세는 findCnt를 사용하여 dfs를 다 돌고 난 뒤 findCnt가 size와 다르다면 모든 구역이 연결되어있는 것이 아니므로 return 해주었습니다.

 

두 그룹의 인구수의 차이의 최솟값을 저장하는 diff변수를 통해 diff변수가 초기값과 같다면 -1을 출력하고, diff의 값이 바뀌었다면 diff값을 출력해주었습니다.

 

❗ Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] popul;
    static ArrayList<Integer>[] list;
    static int diff = Integer.MAX_VALUE;
    static int findCnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        popul = new int[N + 1];
        list = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            popul[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++) {
                int temp = Integer.parseInt(st.nextToken());
                list[i].add(temp);
            }
        }

        for (int i = 1; i <= N / 2; i++) {
            combination(0, 1, new boolean[N + 1], i);
        }

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

    /**
     *
     * @param cnt           뽑은 조합의 개수
     * @param start         출발점
     * @param isSelected    선택 결과
     * @param size          선택 해야하는 개수
     */
    private static void combination(int cnt, int start, boolean[] isSelected, int size) {
        if (cnt == size) {
//            System.out.println(Arrays.toString(isSelected));
            //-----true인 그룹 탐색-------
            int startIndex = getStart(isSelected, true);
            findCnt = 0;
            int pop1 = dfs(startIndex, isSelected, new boolean[N+1], true);
            if(findCnt!=size){
                return;
            }

            //-----false인 그룹 탐색(여집합)-----------
            startIndex = getStart(isSelected, false);
            findCnt = 0;
            int pop2 = dfs(startIndex, isSelected, new boolean[N+1], false);
            if(findCnt!=(N-size)){
                return;
            }

            diff = Math.min(diff, Math.abs(pop1-pop2));

            return;
        }

        for (int i = start; i <= N; i++) {
            isSelected[i] = true;
            combination(cnt + 1, i + 1, isSelected, size);
            isSelected[i] = false;
        }

    }

    /**
     *
     * @param index     방문하는 index
     * @param selected  구성 정보
     * @param visited   방문 여부
     * @param type      탐색할 타입 (true, false)
     * @return
     */
    private static int dfs(int index, boolean[] selected, boolean[] visited, boolean type){
        visited[index] = true;

        int pop = popul[index];
        findCnt++;

        for(int i = 1;i<=N;i++){
            if(!visited[i] && list[index].contains(i) && selected[i]==type){
                pop += dfs(i, selected, visited, type);
            }
        }
        return pop;
    }

    private static int getStart(boolean[] selected, boolean type) {
        for (int i = 1; i < selected.length; i++) {
            if (selected[i] == type) {
                return i;
            }
        }
        return -1;
    }
}