[ 백준 / BOJ 17779 ] 게리멘더링_2 ( 자바 / JAVA )

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

17779번: 게리맨더링 2

문제 설명

재현시 👉 NxN 크기, 구역을 5개의 선거구로 나누어야함

선거구를 나누는 방법

1. 기준점(x,y)와 경계의 길이 $d_1$,$d_2$
   ($d_1$,$d_2$ >= 1, 1 <= x < x+$d_1$+$d_2$ <= N, 1 <= y-$d_1$ < y < y+$d_2$ <= N)
2. 경계선
   1) (x,y),....,(x+$d_1$,y-$d_1$)
   2) (x,y),....,(x+$d_2$,y+$d_2$)
   3) (x+$d_1$,y-$d_1$),...,(x+$d_1$+$d_2$,y-$d_1$+$d_2$)
   4) (x+$d_2$,y+$d_2$),...,(x+$d_2$+$d_1$,y+$d_2$-$d_1$)
3. 경계선과 안에 포함된 구역은 5번 선거구
4. 5번 선거구에 포함되지 않은 구역 (r,c)는
   1번 선거구) 1 <= r < x+$d_1$, 1<= c <= y
   2번 선거구) 1 <= r <= x+$d_2$, y < c <= N
   3번 선거구) x+$d_1$ <= r <= N, 1 <= c < y-$d_1$+$d_2$
   4번 선거구) x+$d_2$ < r <= N, y-$d_1$+$d_2$ <= c <= N

선거구를 나누는 방법 중, 인구가 가장 많은 선거구 - 인구가 가장 적은 선거구의 최솟값을 출력

문제 풀이

4중 포문으로 범위내의 임의의 (x, y, $d_1$, $d_2$)를 선택해 최소값 확인!

코드

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

public class Main_BOJ_17778_게리맨더링_2 {

    static int N;
    static int[][] A;
    static int totalOfPeople = 0;
    static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer;

        N = Integer.parseInt(br.readLine());

        A = new int[N][N];
        for (int i = 0; i < N; i++) {
            stringTokenizer = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                A[i][j] = Integer.parseInt(stringTokenizer.nextToken());
                totalOfPeople += A[i][j];
            }
        }

        for (int x = 0; x < N; x++) {
            for (int y = 0; 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 < 0 || y + d2 >= N) continue;

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

        System.out.println(ans);
    }

    private static void solution(int x, int y, int d1, int d2) {
        boolean[][] borders = new boolean[N][N];

        //경계선
        for (int i = 0; i <= d1; i++) {
            borders[x + i][y - i] = true;
            borders[x + d2 + i][y + d2 - i] = true;
        }

        for (int i = 0; i <= d2; i++) {
            borders[x + i][y + i] = true;
            borders[x + d1 + i][y - d1 + i] = true;
        }

        int[] sumOfPeople = new int[6];

        // 1구역
        for (int i = 0; i < x + d1; i++) {
            for (int j = 0; j <= y; j++) {
                if(borders[i][j]) break;
                sumOfPeople[1] += A[i][j];
            }
        }

        // 2구역
        for (int i = 0; i <= x + d2; i++) {
            for (int j = N - 1; j > y; j--) {
                if(borders[i][j]) break;
                sumOfPeople[2] += A[i][j];
            }
        }

        // 3구역
        for (int i = x + d1; i < N; i++) {
            for (int j = 0; j < y - d1 + d2; j++) {
                if(borders[i][j]) break;
                sumOfPeople[3] += A[i][j];
            }
        }

        // 4구역
        for (int i = x + d2 + 1; i < N; i++) {
            for (int j = N - 1; j >= y - d1 + d2; j--) {
                if (borders[i][j]) break;
                sumOfPeople[4] += A[i][j];
            }
        }

        // 5구역
        sumOfPeople[5] = totalOfPeople;
        for (int i = 1; i < 5; i++) {
            sumOfPeople[5] -= sumOfPeople[i];
        }

        Arrays.sort(sumOfPeople);

        ans = sumOfPeople[5] - sumOfPeople[1] < ans ? sumOfPeople[5] - sumOfPeople[1] : ans;
    }

}