[백준/17471] 게리맨더링(Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/17471
• 분류 : 그래프 탐색, 프루트 포스, BFS
• 풀이 시간 : 75분

문제 해설

1. 총 N개의 구역 (구역 번호 : 1 ~ N)
2. 하나의 구역에는 인구 수 존재
3. N개의 구역을 두 개의 선거구로 나눠야 함
4. 선거구 조건
   1. 최소 1개의 구역을 포함하고 있어야 함
   2. 포함된 구역들은 서로 연결되어 있어야 함
5. 나눠진 두 지역구의 인구 차이의 최솟값은?

Solution

풀이 접근 방법

1. 서로 각기 다른 구역을 가지고 있는 지역구 존재 = Set 사용

2. N개의 구역을 두개로 나눠야 하는데, 최소 1개의 구역을 포함해야 함 = N개 중 1, 2, 3 ...N-1개를 뽑는 조합 사용

   • 1개 뽑는 조합과 N-1개 뽑는 조합의 인구 차 값은 동일함

     집합 : [1, 2, 3, 4, 5]
     
     5개 중 1개를 뽑는 조합 중
     A = [1]가 뽑히면
     B = [2, 3, 4, 5]가 됨
     
     5개 중 4개를 뽑는 조합 중
     A = [2, 3, 4, 5]가 뽑히면
     B = [1]가 됨
     
     지역구에 뽑힌 지역은 다르지만, 두 지역구의 인구 차는 동일

   • 중복 방지를 위해 1개 ~ (N+1)/2개 까지만 뽑음

3. 지역구 내 구역들은 서로 연결되어 있어야 함 = BFS 통하여 확인

   • 다음 방문 노드를 정하는 시점에서 방문 가능한 노드가 다른 지역구에 속해있는지 확인

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Main {
  static int N, minDiff;
  static int[] population;
  static int[][] map;
  static Set<Integer> nodes;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    // 총 지역 수
    N = Integer.valueOf(br.readLine());
    // 지역의 인구 수 배열
    population = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    // 연결되어있는 지역을 표현하기 위한 배열
    map = new int[N][N];
    // 전체 지역 번호 잡합
    nodes = new HashSet<Integer>();
    // 나눠진 선거구의 인구 차이 최솟값을 담기 위한 변수
    minDiff = Integer.MAX_VALUE;

    for (int i = 0; i < N; i++) {
      nodes.add(i);
      String[] info = br.readLine().split(" ");

      // 양방향 그래프 2차차원 배열로 표시
      if (Integer.valueOf(info[0]) > 0) {
        for (int j = 1; j < info.length; j++) {
          int dest = Integer.valueOf(info[j]) - 1;
          map[i][dest] = 1;
          map[dest][i] = 1;
        }
      }
    }

    // 1. 선거구 내 지역이 1개 ~ (N+1)/2개 일 때의 지역 조합 구함
    for (int pick = 1; pick <= (N + 1) / 2; pick++) {
      solution(pick, 0, new boolean[N]);
    }

    minDiff = minDiff == Integer.MAX_VALUE ? -1 : minDiff;
    bw.write(minDiff + "\n");
    bw.flush();
    bw.close();
  }

  static void solution(int pick, int start, boolean[] visited) {
    // 1-2. 다 뽑았을 때
    if (pick == 0) {
      // 2. 지역구 A 집합 구함
      Set<Integer> A = new HashSet<Integer>();

      for (int i = 0; i < N; i++) {
        if (visited[i])
          A.add(i);
      }

      // 3. 지역구 B 집합 구함
      Set<Integer> B = new HashSet<Integer>(nodes);
      B.removeAll(A);

      // 4. 지역구 내 구역이 연결되어있는지 확인
      // 4-1. 지역구 A 연결 확인
      int aValue = isConnected(A, B);
      if (aValue == -1)
        return;

      // 4-2. 지역구 B 연결 확인
      int bValue = isConnected(B, A);
      if (bValue == -1)
        return;

      // 5. 두 선거구의 인구차를 최소 인구차와 비교하여 갱신
      minDiff = Math.min(minDiff, Math.abs(aValue - bValue));

      return;
    }

    // 1-1. 조합 뽑음
    
    for (int i = start; i < N; i++) {
      visited[i] = true;
      solution(pick - 1, i + 1, visited);
      visited[i] = false;
    }

  }

  static int isConnected(Set<Integer> set, Set<Integer> diffSet) {
    // 연결된 구역의 총 인구를 담는 변수
    int connectValue = 0;
    // 이미 방문한 구역인지 확인하기위한 배열
    boolean[] visited = new boolean[N];

    // 연결된 선거구 = 임의의 한 점에서 BFS하면 모든 구역을 방문할 수 있어야 함
    // BFS 후, 방문 못한 구역이 있으면 연결되어있지 않다는 의미
    Iterator<Integer> iter = set.iterator();
    int start = iter.next();

    Queue<Integer> queue = new LinkedList<Integer>();
    queue.add(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
      int current = queue.poll();

      for (int i = 0; i < N; i++) {
        // 서로 연결된 구역이고, 방문한 적이 없고, 다른 선거구에 포함되어있지 않는 구역이라면 탐색
        if (map[current][i] == 1 && !visited[i] && !diffSet.contains(i)) {
          queue.add(i);
          visited[i] = true;
        }
      }
    }

    // 임의의 한 지역을 기준으로 방문 탐색하였을 때
    // 선거구에 포함된 지역이 방문되어있지 않으면 연결 X
    for (Integer n : set) {
      if (!visited[n])
        return -1;
      connectValue += population[n];
    }

    // 모두 방문되었으면 제대로된 선거구의 인구수 리턴
    return connectValue;
  }
}