[백준] 17471 - 게리맨더링 (자바 Java)

[Gold IV] 게리맨더링 - 17471

문제 링크

성능 요약

메모리: 14924 KB, 시간: 136 ms

분류

너비 우선 탐색(bfs), 브루트포스 알고리즘(bruteforcing), 조합론(combinatorics), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 수학(math)

문제

 

첫째 줄에 구역의 개수 N이 주어진다. 둘째 줄에 구역의 인구가 1번 구역부터 N번 구역까지 순서대로 주어진다. 인구는 공백으로 구분되어져 있다.

셋째 줄부터 N개의 줄에 각 구역과 인접한 구역의 정보가 주어진다. 각 정보의 첫 번째 정수는 그 구역과 인접한 구역의 수이고, 이후 인접한 구역의 번호가 주어진다. 모든 값은 정수로 구분되어져 있다.

구역 A가 구역 B와 인접하면 구역 B도 구역 A와 인접하다. 인접한 구역이 없을 수도 있다.

출력

첫째 줄에 백준시를 두 선거구로 나누었을 때, 두 선거구의 인구 차이의 최솟값을 출력한다. 두 선거구로 나눌 수 없는 경우에는 -1을 출력한다.

---

풀이

선거구를 두 개로 나누기 위해 부분집합을 활용한다.

boolean 배열을 통해 부분집합에 포함된 것과 포함되지 않은 것을 각각 bfs를 돌려 연결이 되어 있는지 확인한다.

    static void divide(int depth) {
        if (depth == N + 1) {
            sumT = 0;
            sumF = 0;

            // 공집합 전체집합은 제외
            int cnt1 = 0;
            int cnt2 = 0;
            for (int i = 1; i <= N; i++) {
                if (pick[i])
                    cnt1++;
                if (!pick[i])
                    cnt2++;
            }
            if (cnt1 == N || cnt2 == N)
                return; // 공집합 전체집합이면 제외

            boolean check = false;
            for (int i = 1; i <= N; i++)
                if (pick[i]) {
                    check = bfs(i, true);
                    break;
                }
            if (check) {
                check = false;
                for (int i = 1; i <= N; i++)
                    if (!pick[i]) {
                        check = bfs(i, false);
                        break;
                    }
            }

            if (check) {
                ans = Math.min(ans, Math.abs(sumT - sumF));
            }
            return;
        }

        pick[depth] = true;
        divide(depth + 1);
        pick[depth] = false;
        divide(depth + 1);

    }

둘 다 연결이 되어 있다면 두 선거구에 포함된 인구의 차이를 ans와 비교하여 최소로 만든다.

bfs가 boolean을 반환하도록 하여 연결되어 있으면 true, 아니면 false를 리턴한다.

bfs는 check를 매개변수로 가지는데, check는 부분집합에 포함되었는지 아닌지를 판별하는 boolean 변수다.

    static boolean bfs(int i, boolean check) {
        Queue<Integer> q = new LinkedList<>();
        q.add(i);
        Arrays.fill(visited, false);
        while (!q.isEmpty()) {
            int tmp = q.poll();
            if (visited[tmp])
                continue;
            visited[tmp] = true;
            if (check)
                sumT += val[tmp];
            else
                sumF += val[tmp];
            for (int j = 0; j < adjArr[tmp].length; j++) {
                int link = adjArr[tmp][j];
                if (pick[link] == check && !visited[link]) {
                    q.add(link);
                }
            }
        }

        for (int n = 1; n <= N; n++) {
            if (pick[n] == check && !visited[n])
                return false;
        }
        return true;

    }