백준_17471 게리맨더링(자바) / BFS + 조합

시간 & 메모리 제한

문제

입력 & 출력

예제 입력

BFS + 조합을 통한 문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.InputStreamReader;
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 Back_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 Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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); // 조합을 통한 지역 분리.
        }
 
        if (ans == Integer.MAX_VALUE) {
            ans = -1;
        }
 
       System.out.println(ans);
    }
 
    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) {
        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);
        }
  
        if(!isConnect(positions[B.get(0)].x, B, B.size())) {
            return;
        }
 
        int resultA = 0;
        for (int i = 0; i < A.size(); i++) {
            resultA += positions[A.get(i)].peopleNum;
        }
 
        int resultB = 0;
        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)) {
                if (!visited[i] && arr.contains(i)) {
                    visited[i] = true;
                    count++;
                    q.offer(i);
                }
            }
        }
 
        if (count == size) {
            return true;
        }
        return false;
    }
 
}

 

- 게리 멘더링의 문제를 읽어보면 N개의 갯수를 조합을 이용해서 나눠주는 과정이 필요하고, 이때의 BFS또는 DFS를 이용해서 연결이 되어 있는지 확인후에, 인구의 수를 구한다음 그 차이를 해결하는 문제인거 같습니다.

 

- 이중 ArrayList를 만들어서 문제를 풀었습니다.

 

- Step1. Combi라는 함수를 만들어서 조합을 이용해서 풀었습니다.

 

- Step2. 선택이 완료 되면 게리멘더링이라는 함수를 만들어서 만들어진 ArrayList A를 보냈습니다.

 

- Step3. BFS를 이용해서 A에 들어 있는 것에 대한 연결 여부를 확인했고, A가 아닌 것을 B에 담아준 다음에 B의 연결 여부 역시 확인했습니다.

 

- Step4. 각각의 합을 for문을 이용해서 구했고, Math.abs를 이용해서 차이의 절댓값을 구해줬습니다.