[JAVA] 백준 17471번

www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

💡

1. 선거구 나누기

2. 선거구 유효한지 확인

3. 선거구가 유효할 때 인구 차이 비교

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    
    static int N, min=Integer.MAX_VALUE;
    static int[] people;    // 구역 별 인구
    static boolean[] section;    // true : 선거구 A, false : 선거구 B
    static int[][] path;    // 간선 유무
    
    static ArrayList<Integer> a, b;
    static boolean[] isVisited;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        // 0 dummy
        people = new int[N+1];
        path = new int[N+1][N+1];
        section = new boolean[N+1];
        
        // 구역 별 인구
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) {
            people[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());
                path[i][temp] = 1;
                path[temp][i] = 1;
            }
        }
        
        // 선거구 나누고 min값 찾으러~~~ 0은 dummy니까 1구역부터 시작
        sub(1);
        
        // min값 변동 없을 경우 선거구를 나눌 수 없으므로 -1 출력
        if(min==Integer.MAX_VALUE)    System.out.println(-1);
        else    System.out.println(min);
        
    }
    
    // 로직
    static void sub(int tgtIdx) {
        
        if(tgtIdx == N+1) {
            
            // 초기화
            a = new ArrayList<>();
            b = new ArrayList<>();
            isVisited = new boolean[N+1];
            
            // 선거구 나눠 넣기
            for(int i=1; i<=N; i++) {
                if(section[i])    a.add(i);
                else b.add(i);
            }
            
            // 한쪽으로 몰리면 선거구 나뉜 것 X
            if(a.size()==0 || b.size()==0)    return;
            
            // A, B 각 구역 내 이동 가능한지 확인 
            goA(a.get(0));
            goB(b.get(0));
            
            // min값 비교
            min = Math.min(min, cal());
            return;
        }
        
        section[tgtIdx] = true;
        sub(tgtIdx+1);
        section[tgtIdx] = false;
        sub(tgtIdx+1);
    }
    
    // 두 선거구의 인구 차이 계산
    static int cal() {
        // isVisited에 false가 있으면 각 구역 내 이동할 수 없다는 뜻이므로 선거구 유효 X
        for(int i=1; i<N+1; i++) {
            if(!isVisited[i])    return Integer.MAX_VALUE;
        }
        
        // 선거구 별 인구 수
        int aSum=0, bSum=0;
        for(int i=0; i<a.size(); i++) {
            aSum += people[a.get(i)];
        }
        for(int i=0; i<b.size(); i++) {
            bSum += people[b.get(i)];
        }
        
        // 인구 차이 return
        return Math.abs(aSum - bSum);
    }
    
    // 선거구 A 내 이동 가능 여부 확인
    static void goA(int s) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(s);
        isVisited[s] = true;
        
        while(!queue.isEmpty()) {
            int tmp = queue.poll();
            for(int i=0; i<a.size(); i++) {
                if(path[tmp][a.get(i)] == 1 && !isVisited[a.get(i)]) {
                    queue.offer(a.get(i));
                    isVisited[a.get(i)] = true;
                }
            }
        }
    }
    
    // 선거구 B 내 이동 가능 여부 확인
    static void goB(int s) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(s);
        isVisited[s] = true;
        
        while(!queue.isEmpty()) {
            int tmp = queue.poll();
            for(int i=0; i<b.size(); i++) {
                if(path[tmp][b.get(i)] == 1 && !isVisited[b.get(i)]) {
                    queue.offer(b.get(i));
                    isVisited[b.get(i)] = true;
                }
            }
        }
    }
 
}