[BOJ/GoldIV] 17471. 게리맨더링 - JAVA 자바

17471번: 게리맨더링

• 120ms
• DFS BFS 부분집합

이 문제는 두 개의 선거구로 나누는데 같은 선거구끼리는 서로 인접해야 한다.

1. n개의 구역들을 2개의 선거구로 나누기 ➜ 부분집합 DFS
2. 각각의 선거구 구역들끼리 서로 인접한지 확인 ➜ BFS

두 개의 선거구로 나누는 작업은 부분집합으로 한 선거구에는 반드시 하나의 구역이 포함되어야 한다.

private static void divide(int idx) { 
        if (idx == N) {
            a.clear(); b.clear();
            for (int i = 0; i < N; i++) {
                if (selected[i])  a.add(i);
                else b.add(i);
            }
            if (a.size() == 0 || b.size() == 0)  return;

            if (check(a) && check(b))  // 두 구역이 각각 인접한지 확인
                getDiff(); // 인구차 구하기
            return;
        }

        selected[idx] = true;
        divide(idx + 1);
        selected[idx] = false;
        divide(idx + 1);

    }

 

한 선거구의 구역들 중 하나를 선택하여 해당 구역의 인접리스트를 가져온 후 방문하지 않았고 선거구에 해당하는 구역을 찾아 count를 센다. 선거구에 해당하는 구역수와 count한 수가 같다면 서로 인접한 선거구임을 나타낸다.

private static boolean check(List<Integer> list) {
        Queue<Integer> q = new LinkedList<>();
        visited = new boolean[N];
        visited[list.get(0)] = true;
        q.offer(list.get(0));

        int count = 1; // 방문한 구역 개수
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int i = 0; i < graph.get(cur).size(); i++) {
                int tmp = graph.get(cur).get(i);
                if (list.contains(tmp) && !visited[tmp]) { // 선거구에 해당하고, 아직 미방문
                    q.offer(tmp);
                    visited[tmp] = true;
                    count++;
                }
            }
        }
        if (count == list.size()) // 선거구에 해당하는 구역수와 방문한 구역수가 같은 경우
            return true;
        else
            return false;
    }

첫 시도는 부분집합(DFS) + 유니온파인드를 통해 서로의 루트노드가 같다면 인접한 것으로 구현하였는데 왜인지 자꾸 틀렸다. 반례는 몰?루 ...

 

#소스코드

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

public class Main {

    static int N, result = Integer.MAX_VALUE;
    static int peoples[]; // 구역별 인구수
    static List<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean selected[];
    static boolean visited[];
    static List<Integer> a = new ArrayList<Integer>();
    static List<Integer> b = new ArrayList<Integer>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine()); // 지역 개수
        peoples = new int[N]; // 지역별 인구 수
        selected = new boolean[N]; // 부분집합 만들 때 사용


        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) // 지역별 인구 수 입력
            peoples[i] = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++)
            graph.add(new ArrayList<Integer>());

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int cnt = Integer.parseInt(st.nextToken()); // 인접 구역 수
            for (int j = 0; j < cnt; j++) {
                graph.get(i).add(Integer.parseInt(st.nextToken()) - 1);
            }
        }

        divide(0);

        System.out.println(result == Integer.MAX_VALUE ? -1 : result);

    }

    private static void divide(int idx) { // 선거구 나누기
        if (idx == N) {
            a.clear();
            b.clear();

            for (int i = 0; i < N; i++) {
                if (selected[i])
                    a.add(i);
                else
                    b.add(i);
            }

            if (a.size() == 0 || b.size() == 0) 
                return;


            if (check(a) && check(b)) { // 두 구역이 각각 연결되었는지 확인
                getDiff(); // 인구차 구하기
            }

            return;
        }

        selected[idx] = true;
        divide(idx + 1);
        selected[idx] = false;
        divide(idx + 1);

    }

    private static boolean check(List<Integer> list) {
        Queue<Integer> q = new LinkedList<>();
        visited = new boolean[N];
        visited[list.get(0)] = true;
        q.offer(list.get(0));

        int count = 1; // 방문한 지역 개수
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int i = 0; i < graph.get(cur).size(); i++) {
                int tmp = graph.get(cur).get(i);
                if (list.contains(tmp) && !visited[tmp]) { // 선거구에 해당하고, 아직 미방문
                    q.offer(tmp);
                    visited[tmp] = true;
                    count++;
                }
            }
        }
        if (count == list.size()) // 선거구에 해당하는 지역수와 방문한 지역수가 같은 경우
            return true;
        else
            return false;
    }

    private static void getDiff() { //  선거구의 인구 차 구하기
        // a구역 사람수
        int aCnt = 0, bCnt = 0;
        for (int i = 0; i < N; i++) {
            if (selected[i])
                aCnt += peoples[i];
            else
                bCnt += peoples[i];
        }
        int diff = Math.abs(aCnt - bCnt);
        result = Math.min(result, diff);
    }

}