게리맨더링 - 17471번

---

내 코드

package com.company;

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

public class Main {
    static int N, answer;
    static int[][] arr;
    static int[] p;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N = Integer.parseInt(br.readLine());
        p = new int[N + 1];
        arr = new int[N + 1][N + 1];
        visited = new boolean[N + 1];
        answer = -1;

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            p[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            for (int j = 0; j < x; j++) {
                int y = Integer.parseInt(st.nextToken());
                arr[i][y] = 1;
                arr[y][i] = 1;
            }
        }
        dfs(1, 0);
        System.out.println(answer);
    }

    static void dfs(int index, int x) {
        int a = bfs(x);
        int b = bfs((int) Math.pow(2, N) - 1 - x);
        if (a != -1 && b != -1 && (answer == -1 || answer > Math.abs(a - b))) {
            answer = Math.abs(a - b);
        }

        for (int i = index; i <= N; i++) {
            dfs(i + 1, x + (1 << i - 1));
            dfs(i + 1, x);
        }

    }

    static int bfs(int x) {
        int index = 0;
        for (int i = 1; i <= N; i++) {
            if ((1 << (i - 1) & x) > 0) {
                index = i;
                break;
            }
        }
        Queue<Integer> q = new LinkedList<>();
        q.add(index);
        x -= 1 << (index - 1);
        int total = 0;

        while (!q.isEmpty()) {
            int a = q.poll();
            total += p[a];

            for (int i = 1; i <= N; i++) {
                if (arr[a][i] == 1 && (x & 1 << (i - 1)) > 0) {
                    x -= 1 << (i - 1);
                    q.add(i);
                }
            }
        }
        return x == 0 ? total : -1;
    }
}