boj 17471 게리맨더링

www.acmicpc.net/problem/17471

17471번: 게리맨더링

선거구를 두 구간으로 나누는데 나눠진 구간끼리 연결되어 있어야합니다.

 

dfs기반의 부분집합으로 나눌 수 있는 모든 구간을 확인합니다.

두 구간을 div1, div2라는 리스트를 사용하였고, 구역들끼리 연결되어있는지 bfs를 통해 확인합니다.

구간의 모든 구역끼리 연결되어 있으면 구역들의 합의 최솟값을 갱신합니다.

두 선거구로 나눌 수 없는 경우가 입력으로 주어질 수 있으니 그 때는 -1을 출력합니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    static ArrayList<Integer> graph[] = new ArrayList[11];
    static ArrayList<Integer> div1 = new ArrayList<>();
    static ArrayList<Integer> div2 = new ArrayList<>();
    static int list[] = new int[11];
    static boolean pick[] = new boolean[11];
    static boolean visit[] = new boolean[11];
    static int N, ans = 2147483647;
 
    static boolean bfs(ArrayList<Integer> div, int size, boolean t) {
        Arrays.fill(visit, false);
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(div.get(0));
        visit[div.get(0)] = true;
        int cnt = 0;
        while (!dq.isEmpty()) {
            int x = dq.poll();
            cnt++;
            for (int i = 0; i < graph[x].size(); i++) {
                int next = graph[x].get(i);
 
                if (visit[next] || pick[next] != t)
                    continue;
 
                visit[next] = true;
                dq.add(next);
            }
        }
 
        if (cnt == size)
            return true;
        else
            return false;
    }
 
    static void func(int idx) {
        if (!div1.isEmpty()) {
            for (int i = 1; i <= N; i++) {
                if (!pick[i])
                    div2.add(i);
            }
            
            if(!div2.isEmpty()) {
                if (bfs(div1, div1.size(), true)) {
                    if (bfs(div2, div2.size(), false)) {
                        int sum = 0;
                        for (int i = 0; i < div1.size(); i++) {
                            sum += list[div1.get(i)];
                        }
 
                        for (int i = 0; i < div2.size(); i++) {
                            sum -= list[div2.get(i)];
                        }
 
                        ans = Math.min(ans, Math.abs(sum));
                    }
                }
                div2.clear();
            }
        }
 
        for (int i = idx; i <= N; i++) {
            div1.add(i);
            pick[i] = true;
            func(i + 1);
            pick[i] = false;
            div1.remove(div1.size() - 1);
        }
    }
 
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
 
        int K, v;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            graph[i] = new ArrayList<>();
            while (K-- > 0) {
                v = Integer.parseInt(st.nextToken());
                graph[i].add(v);
            }
        }
    }
 
    static void print() {
        if (ans == 2147483647)
            System.out.println(-1);
        else
            System.out.println(ans);
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(1);
        print();
    }
}