[백준] 17471번 게리맨더링

17471번 게리맨더링

---

1. 이해하기

• 선거구를 둘로 나누는데 나눠진 각 선거구끼리는 연결이 되어야한다.
• 선거구가 둘로 나눠졌으면 그 중에 선거구의 인구수의 차이가 최소가 되는 때를 찾아야 한다.
• 완전 탐색과 bfs를 이용하는 문제

---

2. 구현하기

• select(index,cnt,limit)

  • index를 N+1까지 증가시키면서 그 때의 index를 선택하는 경우와 선택하지 않는 경우로 나눈다. 그리고 그 때의 결과를 비교해 최솟값을 반환한다.

  • index가 N+1에 도달하고 선택한 갯수가 limit이라면 그 경우가 선거구로 나누는 것이 가능한 경우인지 판단한다.

    • 가능하다면 선택된 선거구와 아닌 선거구로 나누어 합을 구하고 그 합들의 차이를 반환한다.

    • 가능하지 않다면 MAX값을 반환한다.

      static int select(int index, int cnt, int limit) {
      if(index == N+1) {
        if(cnt == limit) {
            if(possible()) {
                int sum1 = 0, sum2 = 0;
                for(int i = 1; i <= N; i++) {
                    if(chosen[i]) sum1 += peopleCnt[i];
                    else sum2 += peopleCnt[i];
                }
                return Math.abs(sum1-sum2);
            }
            return MAX;
        }
        return MAX;
      }
      
      int ret = MAX;
      chosen[index] = true;
      int res = select(index+1,cnt+1,limit);
      ret = (ret > res) ? res : ret;
      chosen[index] = false;
      res = select(index+1,cnt,limit);
      ret = (ret > res) ? res : ret;
      return ret;
      }

• possible()

  • 선택된 경우가 가능한지 판단하는 함수이다.
  • 연결 요소의 수가 2개가 아니면 불가능하다고 판단하고 false를 리턴한다. 2개라면 가능한 경우이므로 true를 리턴한다.

    static boolean possible() {
      int cnt = 0;
      boolean[] visited = new boolean[N+1];
      for(int i = 1; i <= N; i++) {
          if(visited[i]) continue;
          bfs(i,chosen[i],visited);
          cnt++;
      }
      if(cnt != 2) return false;
      return true;
    }

• bfs(start,flag,visited)

  • bfs탐색을 하면서 다음에 방문하려고 하는 곳이 현재 방문한 상태와 같은지(선택이 되었거나 안되었거나) 판단하고 방문할지를 결정한다.

---

3. 전체코드

package algo;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Acm17471_게리맨더링 {
    static final int MAX = 987654321;
    static int N;
    static boolean[] chosen;
    static ArrayList<Integer>[] adj;
    static int[] peopleCnt; // 사람 수 저장

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        chosen = new boolean[N+1];
        adj = new ArrayList[N+1];
        peopleCnt = new int[N+1];
        for(int i = 0; i <= N; i++)
            adj[i] = new ArrayList<>();

        for(int i = 1; i <= N; i++)
            peopleCnt[i] = sc.nextInt();

        for(int i = 1; i <= N; i++) {
            int size = sc.nextInt();
            for(int j = 0; j < size; j++) {
                adj[i].add(sc.nextInt());
            }
        }

        int ans = MAX;
        for(int i = 1; i <= (N+1)/2; i++) {
            int res = select(1,0,i);
            ans = (ans > res) ? res : ans;
        }
        if(ans == MAX)
            System.out.println(-1);
        else
            System.out.println(ans);

        sc.close();
    }

    static int select(int index, int cnt, int limit) {
        if(index == N+1) {
            if(cnt == limit) {
                if(possible()) {
                    int sum1 = 0, sum2 = 0;
                    for(int i = 1; i <= N; i++) {
                        if(chosen[i]) sum1 += peopleCnt[i];
                        else sum2 += peopleCnt[i];
                    }
                    return Math.abs(sum1-sum2);
                }
                return MAX;
            }
            return MAX;
        }

        int ret = MAX;
        chosen[index] = true;
        int res = select(index+1,cnt+1,limit);
        ret = (ret > res) ? res : ret;
        chosen[index] = false;
        res = select(index+1,cnt,limit);
        ret = (ret > res) ? res : ret;
        return ret;
    }

    static boolean possible() {
        int cnt = 0;
        boolean[] visited = new boolean[N+1];
        for(int i = 1; i <= N; i++) {
            if(visited[i]) continue;
            bfs(i,chosen[i],visited);
            cnt++;
        }
        if(cnt != 2) return false;
        return true;
    }

    static void bfs(int start, boolean flag, boolean[] visited) {
        Queue<Integer> q = new LinkedList<>();
        visited[start] = true;
        q.add(start);

        while(!q.isEmpty()) {
            int here = q.poll();
            for(int i = 0; i < adj[here].size(); i++) {
                int there = adj[here].get(i);
                if(visited[there] || chosen[there] != flag) continue;
                q.add(there);
                visited[there] = true;
            }
        }
    }
}