문제 분석

백준시는 N개의 구역으로 나누어져 있고, 구역은 1 - N 번까지 번호가 매겨져 있다
구역의 번호를 인덱스로 이용해서 사용하자
구역을 두개의 선거구로 나누어야하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야한다.
선거구의 조건
1. 최소 한개 이상의 지역구를 포함해야한다.
2. 각각의 선거구는 연결되어있어야한다.
이러한 조건을 만족하는 선거구가 있다고 가정할때, 선거구에 포함된 인구의 차이를 최솟값을 구하는 것이 문제의 목표이다.

여기서 조건을 다시 보면, 다음과 같다
1. 최소 한개 이상의 지역구를 포함한 선거구로 이루어져야 한다.
2. 선거구내의 지역구끼리는 연결되어 있어야 한다.

문제 풀이

나는 다음과 같은 과정으로 문제를 풀어나갈 계획이다.
1. 어떤 선거구에 어떤 지역구가 들어갈지 내가 정해줄 수 없기 때문에 이 부분을 조합으로 풀어나갈 것이다. 조합을 이용하여 두 선거구에 들어가는 지역구의 조합을 모두 구해준다.
2. 선거구 선택이 완료된다면 선거구 구성의 조건을 확인해야한다. 최소 한개 이상의 지역구로 이루어진, 선거구여야 한다. 즉, 선거구 하나에 몰빵이 되어있으면 안된다는 소리이다.
3. 앞의 조건을 만족한다면, 선거구내에 있는 지역구끼리 연결되어있는지 확인해야한다. dfs의 경우 하나의 가지만 탐색하기 때문에 연결되어있는 다른 가지에는 바로 도달하지 못한다. 즉 bfs를 통해서 한번에 내가 선택한 지역구를 모두 탐색하고 나오는지만 확인할 것이다.

코드

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

/**
 * @author onyoo
 * @performance
 * @category
 * @note
 * @see
 * 두 선거구로 나누었을때 인구의 차이를 최소화
 * 각각의 선거구는 이어져있어야한다
 * 1. 두 선거구로 나눈다 -> 경우의 수를 구한다
 * 2. 각각의 선거구의 인구 차를 구한다 -> 최솟값보다 크다면 이후 과정을 할 필요가 없다
 * 3. 선별된 선거구가 이어져있는지 확인한다
 * @since 2023-10-10
 **/
public class Main {
    static int p;
    static int[] population; //인구수 저장
    static int[] arr; // 경우의 수 저장
    static ArrayList<Integer>[] list; //인접리스트 저장
    static boolean[] visited;
    static int answer;

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

        p = Integer.parseInt(br.readLine());
        population = new int[p]; // 인구수를 관리하는 배열
        arr = new int[p]; // 인덱스 번호 = 지역구 번호 - 1 , 해당 지역구가 어떤 선거구인지 나타내는 배열 
        list = new ArrayList[p]; // 인접 리스트를 저장할 ArrayList
        answer = Integer.MAX_VALUE; // 최솟값을 저장하기 위한 MAX_VALUE



        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<p;i++){
            population[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0;i<p;i++){
            st = new StringTokenizer(br.readLine()," ");
            int k = Integer.parseInt(st.nextToken());
            list[i] = new ArrayList<>();
            for(int j=0;j<k;j++) list[i].add(Integer.parseInt(st.nextToken())-1);
        }

        dfs(0);
        System.out.println(answer == Integer.MAX_VALUE ? -1 : answer);
        // 정답값이 바뀌지 않았다면, 최솟값이 존재하지 않는 것이기 때문에 -1을 출력합니다
    }

    static void dfs(int depth){
        if(depth == population.length){
            // 모든 선거구가 배정되었다
            // 선거구가 하나에 치우치면 안된다
            // 두 선거구 모두에 최소 하나의 구가 있으면서 인구수 차이가 최소인 경우를 골라내야한다

            int a = 0;
            int b = 0;
            //각 선거구의 인구수를 구하자

            for(int i=0;i<arr.length;i++){
                if(arr[i] == 1) a += population[i];
                else b += population[i];
            }
            int diff = Math.abs(a-b);
            if(a == 0 || b ==  0) return; //하나의 선거구라도 텅 빈다면 잘못된 것
            if(answer < diff) return; // 인구수의 차이가 기존에 가지고 있는 최솟값보다 크다면 더이상 탐색할 필요가 없다
            // 연결 여부 확인하기
            int cnt = 0;
            visited = new boolean[p]; // 방문배열 초기화하기
            for(int i=0;i<list.length;i++){
                if(visited[i]) continue;
                bfs(i,arr[i]);
                cnt++;
            }
            if(cnt == 2) answer = Math.min(answer,diff);

            return;
        }

        arr[depth] = 1;
        dfs(depth+1);
        //1선거구 선택

        arr[depth] = 2;
        dfs(depth+1);
        //2선거구 선택
    }
    static void bfs(int start,int gu){
        Queue<Integer> que = new ArrayDeque();
        que.add(start);

        while(!que.isEmpty()){
            int curr = que.poll();
            visited[curr] = true;

            for(int val : list[curr]){
                if(!visited[val] && arr[val] == gu) que.add(val);
            }
        }
    }
}

마치며

이 문제는 정말 애증의 문제로 여러번 풀었던 문제이다.
조합에 대한 기초가 담겨있고,백트래킹과 완전탐색이 혼합된 문제로 좋은 문제라고 생각한다..