[백준] 17471* 게리맨더링

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int min = Integer.MAX_VALUE;
    static boolean[] selected;
    static int[] population;
    static boolean[][] matrix; // 가중치 없는 그래프
    static boolean[] visit; // 완탐 + 연결
    static ArrayDeque<Integer> q = new ArrayDeque<>();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        matrix = new boolean[N+1][N+1];
        population = new int[N+1];
        selected = new boolean[N+1];
        visit = new boolean[N+1];

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

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

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

        // 부분집합으로 2개 나누기
        // 나눠진 구역끼리 연결 되었는지 확인
        // 연결 되었다면, 두 구역의 차가 가장 적은 거 구하기
        subset(1);

        if(min == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(min);
    }

    static void subset(int index){
        if(index == N+1){
            check();
            return;
        }

        selected[index] = true;
        subset(index+1);

        selected[index] = false;
        subset(index+1);
    }

    static void check(){
        Arrays.fill(visit, false);
        q.clear();

        // A
        for(int i = 1;i<=N;i++){
            if(selected[i]){
                visit[i] = true;
                q.add(i);
                break;
            }
        }
        if(q.size()==0) return;

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

            for(int i=1;i<=N;i++){
                if(!matrix[v][i] || visit[i] || !selected[i]) continue;
                visit[i] = true;
                q.add(i);
            }
        }
        // B
        for(int i = 1;i<=N;i++){
            if(!selected[i]){
                visit[i] = true;
                q.add(i);
                break;
            }
        }

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

            for(int i=1;i<=N;i++){
                if(!matrix[v][i] || visit[i] || selected[i]) continue;
                visit[i] = true;
                q.add(i);
            }
        }

        // 연결 확인
        for(int i=1;i<=N;i++){
            if(!visit[i]) return;
        }

        // 차 구하기
        int sumA=0; int sumB=0;

        for(int i=1;i<=N;i++){
            if(selected[i]) sumA += population[i];
            else sumB += population[i];
        }

        min = Math.min(min, Math.abs(sumA-sumB));
    }
}

dfs

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int min = Integer.MAX_VALUE;
    static boolean[] selected;
    static int[] population;
    static boolean[][] matrix; // 가중치 없는 그래프
    static boolean[] visit; // 완탐 + 연결
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        matrix = new boolean[N+1][N+1];
        population = new int[N+1];
        selected = new boolean[N+1];
        visit = new boolean[N+1];

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

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

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

        // 부분집합으로 2개 나누기
        // 나눠진 구역끼리 연결 되었는지 확인
        // 연결 되었다면, 두 구역의 차가 가장 적은 거 구하기
        subset(1);

        if(min == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(min);
    }

    static void subset(int index){
        if(index == N+1){
            check();
            return;
        }

        selected[index] = true;
        subset(index+1);

        selected[index] = false;
        subset(index+1);
    }

    // sel : A == true, B == false
    static void dfs(int v, boolean sel){
        visit[v] = true;
        for(int i=1;i<=N;i++){
            if(!matrix[v][i] || visit[i] || selected[i] != sel) continue;
            dfs(i, sel);
        }
    }

    static void check(){
        Arrays.fill(visit, false);

        // A
        int a = -1;
        for(int i = 1;i<=N;i++){
            if(selected[i]){
                a=i;
                break;
            }
        }
        if(a==-1) return;
        dfs(a, true);
        
        
        // B
        int b = -1;
        for(int i = 1;i<=N;i++){
            if(selected[i]){
                b=i;
                break;
            }
        }
        if(b==-1) return;
        dfs(b,false);

        // 연결 확인
        for(int i=1;i<=N;i++){
            if(!visit[i]) return;
        }

        // 차 구하기
        int sumA=0; int sumB=0;

        for(int i=1;i<=N;i++){
            if(selected[i]) sumA += population[i];
            else sumB += population[i];
        }

        min = Math.min(min, Math.abs(sumA-sumB));
    }
}