[JAVA] 17471 - 게리맨더링 💛3 : 완전탐색 + DFS로 Connected Component를 카운팅하는 문제

들어가며

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

이 문제.. 입력 부분이 처음엔 좀 이해하기 어렵다. 어려운 문제다. 간단하게 정리하자면 모든 지역은 1 또는 2의 지역으로 나뉘고, 1 또는 2 지역들끼리 묶여있는(Connected Component) 노드들의 가중치 합의 차이값을 구해서 그중 최솟값을 출력하면 되는 문제이다.

본문으로

딱 읽자마자 느낄 수 있는건, 지역이 1또는 2로만 나눠지기에 DFS의 유명한 유형인 Connected Compenet 개수 카운팅 하는 문제다. 근데 보통은 문제에서 상태를 가진 노드들이 정해져서 주어지는데, 이 문제는 어떤 노드가 1 또는 2의 지역인지 모르기 때문에 모든 경우의 수를 구해야 하는 완탐 문제이다. 이렇게 섞은 거는 처음 풀어봤다. 골드 상위권은 확실히 섞는구나..

어쨌든!! 아래와 같이 N의 범위가 10 이하이기 때문에 아래와 같이 시간복잡도 신경 안쓰고 생각을 정리했다.

정확히 계산해보자면 각 지역 선거구를 정해주기(2^N), 각 경우마다 DFS 돌리며 연결성 체크(N^2) 그래서 O(2^N * N^2)로 커보이지만, 1024 * 100 = 10만 정도밖에 안된다! 아래와 같이 완탐으로 정답을 제출했다.

public class Main {

    static int N, ret;
    static Node[] people;
    static List<Integer>[] adjList;

    static class Node {
        int weight;
        int election;

        Node(int weight, int election) {
            this.weight = weight;
            this.election = election;
        }
    }

    static void go(int idx) {
        if (idx == N) {
            if (isOkay()) {
                int one = 0;
                int two = 0;
                for (int i = 1; i <= N; i++) {
                    if (people[i].election == 1) {
                        one += people[i].weight;
                    } else {
                        two += people[i].weight;
                    }
                }
                ret = Math.min(ret, Math.abs(one - two));
            }
            return;
        }

        people[idx + 1].election = 1;
        go(idx + 1);
        people[idx + 1].election = 2;
        go(idx + 1);
    }
    
	// 지역구가 잘 분산되어 있는지.
    static boolean isOkay() {
        int[] visited = new int[N + 4];
        int cnt1 = 0, cnt2 = 0;
        int start1 = -1, start2 = -1;
        for (int i = 1; i <= N; i++) {
            if (people[i].election == 1) {
                cnt1++;
                if (start1 == -1) {
                    start1 = i;
                }
            } else {
                cnt2++;
                if (start2 == -1) {
                    start2 = i;
                }
            }
        }

        if (cnt1 == 0 || cnt2 == 0) { // 하나라도 지역구라도 비어있으면 안된다.
            return false;
        }

        int v1 = find(start1, visited, 1); // 잘 연결되어 있는지 확인하기 위해 DFS 한번만 돌려서 확인
        if (v1 != cnt1) {
            return false;
        }
        int v2 = find(start2, visited, 2);
        if (v2 != cnt2) {
            return false;
        }
        return true;
    }
	
    static int find(int idx, int[] visited, int group) {
        visited[idx] = 1;
        int cnt = 1;
        for (int i = 0; i < adjList[idx].size(); i++) {
            if (visited[adjList[idx].get(i)] == 0 && people[adjList[idx].get(i)].election == group) {
                cnt += find(adjList[idx].get(i), visited, group);
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        people = new Node[N + 4];

        StringTokenizer st = new StringTokenizer(bf.readLine());
        for (int i = 1; i <= N; i++) {
            people[i] = new Node(Integer.parseInt(st.nextToken()), 0);
        }
        adjList = new ArrayList[N + 4];
        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
            StringTokenizer line = new StringTokenizer(bf.readLine());
            int size = Integer.parseInt(line.nextToken());
            for (int j = 0; j < size; j++) {
                adjList[i].add(Integer.parseInt(line.nextToken()));
            }
        }
        ret = Integer.MAX_VALUE;
        go(0);

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


    }
}

 

지역이 1 또는 2 밖에 없기 때문에 아래와 같이 비트마스킹으로도 풀 수 있다.

public class Main {
    static final int INF = 987654321;

    static int n;
    static int[] pop;              // a[i]
    static int[] comp;             // comp[i] = 1이면 그룹1, 0이면 그룹2
    static boolean[] visited;
    static List<Integer>[] adj;

    // 반환: [방문한 정점 수, 인구 합]
    static int[] dfs(int here, int value) {
        visited[here] = true;
        int cnt = 1;
        int sum = pop[here];

        for (int there : adj[here]) {
            if (comp[there] != value) continue;   // 같은 그룹만
            if (visited[there]) continue;
            int[] res = dfs(there, value);
            cnt += res[0];
            sum += res[1];
        }
        return new int[]{cnt, sum};
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine().trim());

        pop = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) pop[i] = Integer.parseInt(st.nextToken());

        adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();

        // 입력은 원래 양방향이 보장되지만, C++ 코드처럼 양방향으로 추가해도 OK.
        // (중복 간선이 생길 수 있어도 visited로 인해 결과는 동일하게 나옴)
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            for (int j = 0; j < m; j++) {
                int temp = Integer.parseInt(st.nextToken());
                adj[i].add(temp);
                adj[temp].add(i);
            }
        }

        int ret = INF;

        // i는 그룹1에 들어갈 정점 비트마스크 (0과 all-1 제외: 두 그룹 모두 비어있지 않게)
        for (int mask = 1; mask < (1 << n) - 1; mask++) {
            comp = new int[n + 1];
            visited = new boolean[n + 1];

            int idx1 = -1, idx2 = -1;

            for (int j = 0; j < n; j++) {
                int node = j + 1;
                if ((mask & (1 << j)) != 0) {
                    comp[node] = 1;
                    idx1 = node;
                } else {
                    comp[node] = 0;
                    idx2 = node;
                }
            }

            int[] g1 = dfs(idx1, 1);
            int[] g2 = dfs(idx2, 0);

            // 두 DFS가 합쳐서 n개를 전부 방문했다면 각 그룹이 내부적으로 연결된 것
            if (g1[0] + g2[0] == n) {
                ret = Math.min(ret, Math.abs(g1[1] - g2[1]));
            }
        }

        System.out.println(ret == INF ? -1 : ret);
    }
}

마무리하며

완탐과 DFS는 친구지만, 이렇게 Connected Component를 섞은 문제는 처음본다. 처음 봤을 때 매우 어려웠지만 개수 카운팅만 잘 해주면 되지 않았나 싶다.

점점 유형이 추가되면서 문제가 어려워진다... 솔직히 많이 어렵다.. 계속 연습해야겠다!! 파이팅!