[JAVA] 백준 게리맨더링2

x = 2, y = 4, d 1  = 2, d 2  = 2 /////////// x = 2, y = 5, d 1  = 3, d 2  = 2 //////////// x = 4, y = 3, d 1  = 1, d 2  = 1

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

 

dfs문제인것처럼 보였으나 완전탐색으로 구현하는 문제였다.

 

경계값 비교 및 break문을 이용하기 위해 역방향으로 탐색하는 방식이 필요했다.

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

public class Main {
    static int N;
    static int[][] grid;
    static int totalPeople = 0;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        grid = new int[N][N];


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

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int d1 = 1; d1 < N; d1++) {
                    for (int d2 = 1; d2 < N; d2++) {
                        if (i + d1 + d2 >= N) continue;
                        if (j - d1 < 0 || j + d2 >= N) continue;

                        basePoint(i, j, d1, d2);
                    }
                }
            }
        }
        System.out.println(min);
    }

    static void basePoint(int r, int c, int d1, int d2) {
        int[][] div = new int[N][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)
        */
        for (int i = 0; i <= d1; i++) {//1번,4번
            div[r + i][c - i] = 5;
            div[r + d2 + i][c + d2 - i] = 5;
        }
        for (int i = 0; i <= d2; i++) {//2,3번
            div[r + i][c + i] = 5;
            div[r + d1 + i][c - d1 + i] = 5;
        }
        int[] sum = new int[5];

//1선거구
        for (int i = 0; i < r + d1; i++) {
            for (int j = 0; j <= c; j++) {
                if (div[i][j] == 5) break;
                sum[0] += grid[i][j];
            }
        }
//2선거구
        for (int i = 0; i <= r + d2; i++) {
            for (int j = N - 1; j > c; j--) {
                if (div[i][j] == 5) break;
                sum[1] += grid[i][j];
            }
        }
//3선거구
        for (int i = r + d1; i < N; i++) {
            for (int j = 0; j < c - d1 + d2; j++) {
                if (div[i][j] == 5) break;
                sum[2] += grid[i][j];
            }
        }
//4선거구
        for (int i = r + d2 + 1; i < N; i++) {
            for (int j = N - 1; j >= c - d1 + d2; j--) {
                if (div[i][j] == 5) break;
                sum[3] += grid[i][j];
            }
        }

        //5선거구 = total-(1,2,3,4선거인수)
        sum[4] = totalPeople;
        for (int i = 0; i < 4; i++) sum[4] -= sum[i];


        //최대-최소
        Arrays.sort(sum);

        min = Math.min(min, sum[4] - sum[0]);
    }
}