백준 17471 게리맨더링

백준 17471 게리맨더링

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

문제 풀이법

1. 두개의 선거구로 나누기
2. 각 선거구의 원소들이 서로 연결되었는지 확인하기
3. 연결되었을 경우 선거구 별 인구수 차이를 구한 후 최솟값 갱신하기

코드 설명

선거구는 최소 하나 이상의 구역을 가지고 있으므로 선거구는 1개에서 최대 N-1개의 구역을 갖고 있습니다. 조합을 사용해서 1 ~ N-1개의 A 선거구 리스트를 구한 후에 나머지 포함되지 않는 구역은 B선거구 리스트에 넣습니다. 이후 A 선거구 리스트와 B 선거구 리스트에 들어있는 원소들이 서로 연결되어있는지 확인하기 위해 BFS를 사용합니다.

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
    
    static int n;
    static int[] p;
    static int min = Integer.MAX_VALUE;
    static int[][] map;
    static List<Integer> A;

    public static void main (String[] args) throws java.lang.Exception
    {
        System.setIn(new FileInputStream("input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        p = new int[n];
    
        for (int i = 0; i< n; i++) {
            p[i] = Integer.parseInt(st.nextToken());

        }
        
        map = new int[n][n];
        for (int i = 0; i< n; i++) {
            st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken());
            for (int j = 0; j< cnt; j++) {
                int x = Integer.parseInt(st.nextToken());
                map[i][x - 1] = 1;
                map[x - 1][i] = 1;
            }
        }

        for (int i = 1; i<= n - 1 ; i++) {
            A = new ArrayList<>();
            comb(i, 0, 0);
        }

        if (min == Integer.MAX_VALUE) {
            System.out.println("-1");
        } else {
            System.out.println(min);
        }
    }

    static void comb(int goal, int l, int start) {
        if (l == goal) {
            
            List<Integer> B = new ArrayList<>();
    
            for (int i = 0; i< n; i++) {
                if (!A.contains(i)) {
                    B.add(i);
                    
                }
            }

            //연결성
            if (bfs(A) && bfs(B)) {
                int aCnt = 0;
                int bCnt = 0;
                for (int i = 0; i< A.size(); i++) {
                    aCnt += p[A.get(i)];
                }

                for (int i = 0; i< B.size(); i++) {
                    bCnt += p[B.get(i)];
                }
                
                

                min = Math.min(min, Math.abs(aCnt - bCnt));   
            } 
            
            return;
        }
        
        for (int i = start; i<n; i++) {
            A.add(l,i);
            comb(goal, l + 1, i + 1);
            A.remove(A.size() - 1);
        }
        
    }

    static boolean bfs(List<Integer> l) {
        Queue<Integer> q = new LinkedList<>();

        boolean[] visit = new boolean[n];
        int first = l.get(0);
        q.add(first);
        visit[first] = true;
        int cnt = 0;

        while(!q.isEmpty()) {
            int now = q.poll();
            cnt++;
            for (int i = 0; i< n;i++ ) {
                if (now != i && map[now][i] == 1 && !visit[i] && l.contains(i)) {
                    visit[i] = true;
                    q.add(i);
                }
            }
        }
        
        if (cnt == l.size()) {
            return true;
        } 

        return false;
    }


}