백준 17779 - 게리멘더링 2

9시뮬레이션

import java.util.Scanner;

public class Main{

    static int N;
    static int[][] map;
    static int[][] tempMap;
    static int d1, d2, x1, y1;
    static int min = 99999;
    static int max = 0;
    static int result = 9999;

    public static void main(String[] args){

        // 1. init
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N+1][N+1];
        tempMap = new int[N+1][N+1];

        for(int i=1; i<N+1; i++){
            for(int j=1; j<N+1; j++){
                map[i][j] = sc.nextInt();
            }
        }

        // 2. d1, d2, x, y 만들기
        boundary();

        System.out.println(result);



    }

    static void boundary(){

        for(int i=1; i<=N; i++){
            d1 = i;
            for(int j=1; j<=N; j++){
                d2 = j;
                for(int x =1; x<=N; x++){
                    if(x+d1+d2 >= N) continue;
                    x1 = x;
                    for(int y=1; y<=N; y++){
                        if( 1 > y-d1 || y+d2 > N) continue;
                        y1 = y;
                        tempMap = new int[N+1][N+1];
                        fiveBoundary();
                        divideMap();
                        result = Math.min(result,cal());
                    }
                }
            }
        }

    }

    static void fiveBoundary(){

        for(int i=0; i<=d1; i++){
            tempMap[x1+i][y1-i] = 5;
            tempMap[x1+d2+i][y1+d2-i]=5;
        }

        for(int i=0; i<=d2; i++){
            tempMap[x1+i][y1+i] = 5;
            tempMap[x1+d1+i][y1-d1+i] = 5;
        }

        for(int i = 0; i < d2; i++){
            int t = 1;
            while(tempMap[x1 + i + t][y1 + i] != 5){
                tempMap[x1 + i + t][y1 + i] = 5; t++;
            }
        }

        for(int i = 0; i < d1; i++){
            int t = 1;
            while(tempMap[x1 + i + t][y1 - i] != 5){
                tempMap[x1 + i + t][y1 - i] = 5; t++;
            }
        }

    }


    static void divideMap(){

        // 1번 선거구
        for(int r=1; r<x1+d1; r++){
            for(int c=1; c<=y1; c++){
                if(tempMap[r][c] == 5) continue;
                tempMap[r][c] = 1;
            }
        }

        // 2번 선거구
        for(int r=1; r<=x1+d2; r++){
            for(int c=y1+1; c<=N; c++){
                if(tempMap[r][c] == 5) continue;
                tempMap[r][c] = 2;
            }
        }

        // 3번 선거구
        for(int r=x1+d1; r<=N; r++){
            for(int c=1; c<y1-d1+d2; c++){
                if(tempMap[r][c] == 5) continue;
                tempMap[r][c] = 3;
            }
        }

        // 4번 선거구
        for(int r=x1+d2+1; r<=N; r++){
            for(int c=y1-d1+d2; c<=N; c++){
                if(tempMap[r][c] == 5) continue;
                tempMap[r][c] = 4;
            }
        }

    }

    static int cal(){
        int a=0, b=0, c=0, d=0, e=0;
        max = 0;
        min = 99999;
        for(int i=1; i<N+1; i++){
            for(int j=1; j<N+1; j++){
                if(tempMap[i][j] == 1){
                    a += map[i][j];
                } else if(tempMap[i][j] == 2){
                    b += map[i][j];

                } else if(tempMap[i][j] == 3){
                    c += map[i][j];

                } else if(tempMap[i][j] == 4){
                    d += map[i][j];

                } else {
                    e += map[i][j];
                }
            }
        }

        if( a > max) max = a;
        if( b > max) max = b;
        if( c > max) max = c;
        if( d > max) max = d;
        if( e > max) max = e;

        if( min > a ) min = a;
        if( min > b ) min = b;
        if( min > c)  min = c;
        if( min > d)  min = d;
        if (min > e)  min = e;

        return max-min;

    }
}