[백준 JAVA] 17779 : 게리멘더링 2

[백준 17779] 게리먼더링 2 : https://www.acmicpc.net/problem/17779

---

문제 조건 정리

 

1. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다.
   구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다.
   선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다.
   구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다.
   중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.
   
   
2. 선거구를 나누는 방법은 다음과 같다.
   기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
   다음 칸은 경계선이다.
   1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
      
      경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
      
      
   5. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
      • 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
      • 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
      • 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
      • 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

 (x, y) = (2, 4) 의 기준점에서

1. 좌하(d1) 2칸, (4, 2)
2. 우하(d2) 2칸, (6, 4)
3. 우상(d1) 2칸, (4, 6)
4. 좌상(d2) 2칸, (2, 4)

이동하며 5구역의 경계를 만듦

좌측 이동 -y

우측 이동 +y

상측 이동 -x

하측 이동 +x

 

목표 : 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값 구하기

---

입력

 

1. 첫째 줄에 재현시의 크기 N이 주어진다.
2. 둘째 줄부터 N개의 줄에 N개의 정수가 주어진다.
3. r행 c열의 정수는 A[r][c]를 의미한다.

• 5 ≤ N ≤ 20
• 1 ≤ A[r][c] ≤ 100

---

문제를 풀어보며

 

1. 인덱스를 0부터 하면 헷갈릴 것 같아서 1부터 하기로 함.
   
   
2. 4중 반복문을 통해서 5번 구역의 경계선을 먼저 정하기로 함.
   5번 구역의 경계선을 정할 때, 각 반복문의 조건을 설정하려니 복잡했음.
   문제에서 경계선을 위해 주어진 조건을 반복문 가장 내부에 배치해서 쉽게 해결했음.
   
   
3. 5번 구역의 경계를 그리는 것은 예제를 통해서 쉽게 해결했음.
   그럼에도 해결이 되지 않았는데 문제는 5번 구역 경계선 내부를 5번 구역으로 설정하지 않은 문제였음.
   5번 구역이 정확히 표현되지 않으면 나머지 구역들을 계산하는 과정에서 5번 구역을 인식하지 못하는 문제가 생겼음.
4. 문제에서 가장 까다로운 부분은 5번 구역을 제외한 각 영역을 올바르게 나눌 수 있는 인덱스를 정확히 입력하는 것이었음.
   너무 헷갈려서 종이에 그림을 그리면서 진행했음.
   결과적으로는 5번 구역을 먼저 체크해 둔다면, 나머지 구역들도 쉽게 구할 수 있었음.

 

---

코드

 

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 백준 17779: 게리맨더링2
 * 1. x, y, d1, d2를 모든 가능한 값으로 완전탐색.
 * 2. 5번 구역 경계선 설정 -> 내부 채우기.
 * 3. 남은 지역을 1~4 구역 부등식에 따라 설정.
 * 4. 각 구역 인구수 계산 -> 최댓값-최솟값 갱신.
 */
public class BJ17779_2 {
    static int N;
    static int[][] map;
    static int totalPopulation;
    static int answer = Integer.MAX_VALUE;

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

        map = new int[N + 1][N + 1];
        totalPopulation = 0;

        for (int r = 1; r <= N; r++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int c = 1; c <= N; c++) {
                map[r][c] = Integer.parseInt(st.nextToken());
                totalPopulation += map[r][c];
            }
        }

        // 1. x, y, d1, d2 완전탐색
        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= N; y++) {
                for (int d1 = 1; d1 <= N; d1++) {
                    for (int d2 = 1; d2 <= N; d2++) {
                        if (x + d1 + d2 > N) continue;
                        if (y - d1 < 1) continue;
                        if (y + d2 > N) continue;

                        divideAndCalc(x, y, d1, d2);
                    }
                }
            }
        }

        System.out.println(answer);
    }

    static void divideAndCalc(int x, int y, int d1, int d2) {
        // 5번 구역 표시를 위한 배열
        int[][] area = new int[N + 1][N + 1];

        // 1) 경계선 5로 표시
        for (int i = 0; i <= d1; i++) {
            area[x + i][y - i] = 5;
        }
        for (int i = 0; i <= d2; i++) {
            area[x + i][y + i] = 5;
        }
        for (int i = 0; i <= d2; i++) {
            area[x + d1 + i][y - d1 + i] = 5;
        }
        for (int i = 0; i <= d1; i++) {
            area[x + d2 + i][y + d2 - i] = 5;
        }

        // 2) 5번 구역 채우기
        for (int r = x + 1; r < x + d1 + d2; r++) {
            boolean toggle = false;
            for (int c = 1; c <= N; c++) {
                if (area[r][c] == 5) toggle = !toggle;
                if (toggle) area[r][c] = 5;
            }
        }

        // 3) 1~4번 구역 채우기
        // area[r][c]가 아직 0인 칸을 부등식에 따라 1~4로 채우기
        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                if (area[r][c] != 0) continue;

                // 구역 1
                if (1 <= r && r < x + d1 && 1 <= c && c <= y) {
                    area[r][c] = 1;
                    // 구역 2
                } else if (1 <= r && r <= x + d2 && y < c && c <= N) {
                    area[r][c] = 2;
                    // 구역 3
                } else if (x + d1 <= r && r <= N && 1 <= c && c < y - d1 + d2) {
                    area[r][c] = 3;
                    // 구역 4
                } else if (x + d2 < r && r <= N && (y - d1 + d2) <= c && c <= N) {
                    area[r][c] = 4;
                }
            }
        }

        boolean flag = false;

        for (int r = 1; r <= N; r++) {
            flag = false;
            for (int c = 1; c <= N; c++) {
                if (area[r][c] == 5) {
                    flag = true;
                    continue;
                }

                // 구역 1
                if (!flag && 1 <= r && r < x + d1 && 1 <= c && c <= y) {
                    area[r][c] = 1;
                    // 구역 2
                } else if (flag && 1 <= r && r <= x + d2 && y < c) {
                    area[r][c] = 2;
                    // 구역 3
                } else if (!flag && x + d1 <= r && r <= N && 1 <= c && c < y - d1 + d2) {
                    area[r][c] = 3;
                    // 구역 4
                } else if (flag && x + d2 < r && r <= N && y - d1 + d2 <= c) {
                    area[r][c] = 4;
                }
            }
        }

        // 4) 각 구역 인구수 계산
        int[] population = new int[6];

        for (int r = 1; r <= N; r++) {
            for (int c = 1; c <= N; c++) {
                int a = area[r][c];
                population[a] += map[r][c];
            }
        }

        // 최소, 최대
        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= 5; i++) {
            max = Math.max(max, population[i]);
            min = Math.min(min, population[i]);
        }
        answer = Math.min(answer, max - min);
    }
}

 

---

문제를 풀고 난 후

게리맨더링이라는 용어는 미국 메사추세츠 주시사였던 엘브리지 게리(E. Gerry)가 1812년의 선거에서 자기 당에게 유리하도록 선거구를 정했는데 그 부자연스러운 형태가 샐러맨더(salamander, 불속에 산다는 그리스 신화의 불도마뱀)와 비슷한 데서 유래하였다.

 

끝!

 

(+ 25.04.06) 코드 수정