[BOJ] 17471 게리맨더링

접근 방법

BFS와 브루트포스로 풀어야하는 문제
1. 조합으로 구역을 나눠준다. (true/false로 나눠줬음)
2. 한 구역과 다른 구역 두 번의 큐를 돌리면서 모든 정점을 방문하는지 확인
3. 모두 방문하면 두 구역 인구 계산

결국 그래프 순회니까 BFS/DFS를 활용해야한다는 사실을 몰랐다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution17471 {
    static int n, min = Integer.MAX_VALUE;
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
    static boolean[] visited;
    static int[] p;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        p = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            p[i] = Integer.parseInt(st.nextToken());
        }
        for(int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            for(int j = 0; j < l; j++) {
                adj.get(i).add(Integer.parseInt(st.nextToken())-1);
            }
        }

        visited = new boolean[n];
        dfs(0, 0);
        if(min == Integer.MAX_VALUE) {
            System.out.println("-1");
        } else {
            System.out.println(min);
        }
    }

    static void dfs(int idx, int depth) {
        if(depth > 0) {
            if(check()) {
                cal();
            }
        }
        if(depth == n) {
            return;
        }

        for(int i = idx; i < n; i++) {
            if(!visited[i]) {
                visited[i] = true;
                dfs(i+1, depth+1);
                visited[i] = false;
            }
        }
    }

    static boolean check() {
        boolean[] c = new boolean[n];

        int cnt1 = -1;
        int cnt2 = -1;
        for(int i = 0; i < n; i++) {
            if(visited[i]) cnt1 = i;
            else cnt2 = i;
        }
        if(cnt1 == -1 || cnt2 == -1) {
            return false;
        }

        Queue<Integer> q = new LinkedList<>();
        c[cnt1] = true;
        q.add(cnt1);
        while (!q.isEmpty()) {
            int now = q.poll();
            for(int i = 0; i < adj.get(now).size(); i++) {
                int next = adj.get(now).get(i);
                if(visited[now] != visited[next]) continue;
                if(c[next]) continue;
                c[next] = true;
                q.add(next);
            }
        }

        c[cnt2] = true;
        q.add(cnt2);
        while (!q.isEmpty()) {
            int now = q.poll();
            for(int i = 0; i < adj.get(now).size(); i++) {
                int next = adj.get(now).get(i);
                if(visited[now] != visited[next]) continue;
                if(c[next]) continue;
                c[next] = true;
                q.add(next);
            }
        }

        for(int i = 0; i < n; i++) {
            if(!c[i]) return false;
        }

        return true;
    }

    static void cal() {
        int d1 = 0;
        int d2 = 0;
        for(int i = 0; i < n; i++) {
            if(visited[i]) d1 += p[i];
            else d2 += p[i];
        }
        min = Math.min(min, Math.abs(d1-d2));
    }

}