[백준 17471] - 게리멘더링(JAVA)[골드4]

문제

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

17471번: 게리맨더링

 

문제 풀이

접근 방법에 대해서 많은 고민을 했다.

우선 지역구를 나누는 방법에 대해서 고민을 했는데,

1. 조합을 써서 A와 B 지역구를 나누기
2. 브루트포스로 나누기

두 방법 모두 하나의 지역을 정하면 나머지 구역의 지역을 결정 지을 수 있다.

브루트포스보단 코드적으로 깔끔한 조합을 사용해서 구역을 나눴다.

구역을 나눴다면 이젠 나눈 구역의 지역들이 연결되어 있는지를 확인해야한다.

여러 방법이 있지만 나는 BFS를 이용해서 지역들이 서로 연결되어 있는지 확인했다.

이제 A와 B의 구역이 서로 연결되어있는것을 확인했다면 구역의 인구차이를 계산해서 계속해서 업데이트 해주면 끝이다.

 

요약을 하자면

1. 구역을 나누는 방법은 조합을 써서 나눔.
2. 구역을 나눴다면 서로의 구역이 연결되어 있는지 확인
3. 연결되어 있다면 인구차이를 계산

인구차이를 계산하는 과정에서 자바가 아직 어색해서 Collections의 배열 합을 계산하는 고차함수가 있을텐데

아직 알지 못해서 저렇게 코드를 작성해서 더해줬는데.. 이 부분이 조금 아쉽다.

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static BufferedReader br;
    static StringTokenizer st;

    static int[] graph;
    static boolean[] visit;

    static int answer = Integer.MAX_VALUE;
    static ArrayList<Integer> other = new ArrayList<>();
    static ArrayList<Integer> my = new ArrayList<>();

    static ArrayList<ArrayList<Integer>> list;

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

    public static void input() throws IOException {
        n = Integer.parseInt(st.nextToken()); // 구역 수
        graph = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        list = new ArrayList<>(n + 1);
        for (int i = 1; i <= n; i++) {
            graph[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int amount = Integer.parseInt(st.nextToken());
            for (int j = 0; j < amount; j++) {
                int area = Integer.parseInt(st.nextToken());
                list.get(i).add(area);
            }
        }
        for (int i = 1; i < n; i++) {
            init();
            combination(i, 0, 1);
        }
        if (answer == Integer.MAX_VALUE) System.out.print(-1);
        else System.out.print(answer);
    }

    public static void combination(int limit, int count, int cur) { //뽑아야할 것
        if (count == limit) { //다 뽑았다는 뜻.
            other.removeAll(my);
            if (isConnected(my) && isConnected(other)) { //조합에 대해서 연결된것인지 확인 .. 그러면 반대편도 확인해야하지않나?
                int myPeople = 0;
                int otherPeople = 0;
                for (int m : my) {
                    myPeople += graph[m];
                }
                for (int o : other) {
                    otherPeople += graph[o];
                }
                answer = Math.min(answer, Math.abs(myPeople - otherPeople));
            }
            init();
            return;
        }
        for (int i = cur; i <= n; i++) {
            my.add(i);
            combination(limit, count + 1, i + 1);
            my.remove(my.size() - 1);
        }
    }

    public static void init() {
        other.clear();
        for (int i = 1; i <= n; i++) {
            other.add(i);
        }
    }

    public static boolean isConnected(ArrayList<Integer> ary) {
        //s에 들어간곳끼리는 연결된곳이 확실하니 다른 집합을 확인해야함.
        visit = new boolean[n + 1];
        int count = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(ary.get(0));
        while (!q.isEmpty()) {
            int now = q.poll();
            if (visit[now]) continue;
            count++;
            visit[now] = true;
            for (int i = 0; i < list.get(now).size(); i++) {
                int next = list.get(now).get(i);
                if (ary.contains(next) && !visit[next]) { //구역에 포함되어있고, 방문안한곳이라면
                    q.add(next);
                }
            }
        }
        if (count == ary.size()) return true;
        return false;
    }
}