[백준 17471] 게리맨더링 - JAVA

BOJ Link

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

 

풀이 과정

dfs/bfs 두번 + 조합 문제이다. 

 

문제에선 요구하진 않지만, 비트마스킹으로 풀이했다. N < 10이래서 딱 떠올랐다.

 

1. A선거구에 포함될 구역을 조합으로 뽑는다. -> bit의 dep번째 자리에 0 또는 1을 쌓아가며 뽑는다.

pick(bit, dep + 1);
pick(bit | (1 << dep), dep + 1);

 

2. A선거구에 포함되지 않은 B선거구 구역을 XOR 연산으로 뽑는다.

int a = bfs(bit);
int b = bfs(compbit ^ bit);

 

여기서 combit는 왼쪽 기준으로 2~N+1번째 자리가 모두 1인 비트이다.

(1번째 비트는 padding 을 위해 비웠는데 더 불편했다..)

for (int i = 1; i <= N; i++) compbit |= 1 << i;

 

3. 비트 마스킹한 변수를 기반으로, 0이 마킹된 비트를 찾아 queue에 넣고 bfs한다. (1: 방문함 0:방문하지 않음)

int ptotal = 0;
for (int i = 1; i <= N; i++) {
    if ((bit | 1 << i) != bit) {
        bit |= 1 << i;
        ptotal += popul[i];
        q.offer(i);
        break;
    }
}

 

탐색 전에 원소가 없다면, 한 선거구가 아무 구역도 포함하지 않음을 뜻한다. 정답에서 제외한다.

if (q.isEmpty()) return 0;

 

탐색 이후, compbit와 같으면 유효하다고 판별한다. -> 모두 1인 combit와 같다는 것은 모두 방문한 것임을 의미한다.

즉, 조합으로 뽑은 A선거구 안의 구역이 모두 인접함을 뜻한다.

return compbit == bit ? ptotal : 0;

 

4. 이후 둘다 유효하다면 정답 후보로 넣는다.

if (a != 0 && b != 0) ans = Math.min(Math.abs(a - b), ans);

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    static int N, ans = Integer.MAX_VALUE, compbit, popul[];
    static boolean adj[][];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        popul = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= N; i++) popul[i] = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++) compbit |= 1 << i;

        adj = new boolean[N + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            for (int j = 0; j < M; j++) {
                int t = Integer.parseInt(st.nextToken());
                // 양방향 그래프임
                adj[i][t] = true;
                adj[t][i] = true;
            }
        }

        pick(0, 1);
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }

    public static void pick(int bit, int dep) {

        if (dep == N + 1) {
            int a = bfs(bit);
            int b = bfs(compbit ^ bit);

            // bfs 유효하지 않을 시 0 리턴 -> 각 구역의 인구수는 1 이상이므로, 유효할 때 0이 나올 수 없음
            if (a != 0 && b != 0) ans = Math.min(Math.abs(a - b), ans);
            return;
        }

        pick(bit, dep + 1);
        pick(bit | (1 << dep), dep + 1);

    }

    public static int bfs(int bit) {

        Queue<Integer> q = new ArrayDeque<>();

        int ptotal = 0;
        for (int i = 1; i <= N; i++) {
            if ((bit | 1 << i) != bit) {
                bit |= 1 << i;
                ptotal += popul[i];
                q.offer(i);
                break;
            }
        }
        if (q.isEmpty()) return 0;

        while (!q.isEmpty()) {
            int now = q.poll();

            for (int i = 1; i <= N; i++) {
                if ((bit | 1 << i) != bit && adj[now][i]) {
                    bit |= 1 << i;
                    q.offer(i);
                    ptotal += popul[i];
                }
            }
        }

        return compbit == bit ? ptotal : 0;
    }
}