[BOJ] 17779 게리맨더링 2 (Java)

1. 문제 링크

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

17779번: 게리맨더링 2

 

2. 접근법

1. 4개의 기준점 구하기

  1.1. board의 모든 점을 순회하며 기준점(x, y)을 잡는다.

  1.2. 기준점을 기준으로 범위를 넘어가지 않는 d1, d2 값을 설정해 나머지 3개의 기준점을 잡는다.

  1.3. 4개의 기준점은 point[][]에 저장

 

2. 구한 4개의 기준점을 기준으로 경계선 여부를 isBorder[][]에 저장

 

3. 각 선거구의 인구수 구하기

  3.1. 1~4번 선거구인 경우, 이중 for문으로 해당 선거구 구역을 돌다가 isBorder[][]를 만나면 넘어가기

  3.2. 5번 선거구인 경우, 전체 인구수에서 1~4번 인구수의 합을 빼서 구하기

 

4. 답 구하기

  4.1. 각 선거구의 합계를 담은 populaiton[]을 정렬 후, 가장 큰 값에서 가장 작은 값을 빼서 ans에 최솟값이 담기도록 업데이트하기

 

3. 코드

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

// 게리맨더링 2

public class BJ17779 {

    static int n;
    static int d1, d2;
    static int totalPopulation;
    static int ans = Integer.MAX_VALUE;
    static int[][] board;
    static int[][] point = new int[4][2];       // 기준점 4개
    static boolean[][] isBorder;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n+1][n+1];

        StringTokenizer st;
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= n; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                totalPopulation += board[i][j];
            }
        }

        solution();
        System.out.println(ans);
    }

    private static void solution() {

        // x, y, d1, d2 값에 따라 선거구 나누기
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                point[0][0] = i;
                point[0][1] = j;

                d1 = 1;
                while(true) {
                    if(point[0][0] + d1 > n || point[0][1] - d1 <= 0) break;

                    point[1][0] = point[0][0] + d1;
                    point[1][1] = point[0][1] - d1;

                    d2 = 1;
                    while(true) {
                        if(point[0][0] + d2 > n || point[0][1] + d2 > n) break;

                        point[2][0] = point[0][0] + d2;
                        point[2][1] = point[0][1] + d2;
                        
                        if(point[1][0] + d2 > n || point[1][1] + d2 > n) break;

                        point[3][0] = point[1][0] + d2;
                        point[3][1] = point[1][1] + d2;

                        // isBorder[][]에 경계선 체크하기
                        checkBorder(d1, d2);

                        // 나누어진 선거구에 따라 각 선거구의 인구수 구하기
                        calculatePopulation();
                
                        d2++;
                    }

                    d1++;
                }
            }
        }
    }

    private static void calculatePopulation() {

        int[] population = new int[5];      // 다섯 개의 선거구의 각 인구수의 합

        // 1번 선거구
        for(int i = 1; i < point[1][0]; i++) {
            for(int j = 1; j <= point[0][1]; j++) {
                if(isBorder[i][j]) break;
                population[0] += board[i][j];
            }
        }
        // 2번 선거구
        for(int i = 1; i <= point[2][0]; i++) {
            for(int j = n; j > point[0][1]; j--) {
                if(isBorder[i][j]) break;
                population[1] += board[i][j];
            }
        }
        // 3번 선거구
        for(int i = point[1][0]; i <= n; i++) {
            for(int j = 1; j < point[3][1]; j++) {
                if(isBorder[i][j]) break;
                population[2] += board[i][j];
            }
        }
        // 4번 선거구
        for(int i = point[2][0] + 1; i <= n; i++) {
            for(int j = n; j >= point[3][1]; j--) {
                if(isBorder[i][j]) break;
                population[3] += board[i][j];
            }
        }
        // 5번 선거구
        population[4] = totalPopulation;
        for(int i = 0; i <= 3; i++) {
            population[4] -= population[i];
        }

        Arrays.sort(population);
        ans = Integer.min(ans, population[4] - population[0]);
    }

    private static void checkBorder(int d1, int d2) {

        isBorder = new boolean[n+1][n+1];

        for(int i = 0; i <= d1; i++) {
            isBorder[point[0][0] + i][point[0][1] - i] = true;
            isBorder[point[2][0] + i][point[2][1] - i] = true;
        }

        for(int i = 0; i <= d2; i++) {
            isBorder[point[0][0] + i][point[0][1] + i] = true;
            isBorder[point[1][0] + i][point[1][1] + i] = true;
        }
    }

}

 

4. 막힌 부분

2번, 4개의 기준점까지는 잘 구했다. 근데 인구수 합 구하는 거에서 한참 해맸다 ㅠ

이중 for문을 돌면, 어쨌든 구역이 직사각형 형태일텐데, 아래와 같이 경계선과 경계선 내부의 영역을 구할 수 있다고 생각했다. 바본가...

그럼 나머지 영역을 구해서 5번 영역을 빼야 하나?

for문으로 직사각형 영역을 잡고, 경계선을 만났을 때 break하자.

그래서 isBorder[][]를 만들어서 1~4번 영역부터 구했다.

 

사실 처음에 5번 선거구가 경계선을 포함한다는 조건도 놓쳤었다..ㅋㅋ

 

논리적으로 생각하고 풀어 소영아!!!!