게리맨더링2

게리맨더링2

import java.util.Arrays;
import java.util.Scanner;

public class Main_게리맨더링2 {
    static final int INF = 987654321;
    static int N;
    static int arr[][] = new int[20][20];
    static int Mark[][] = new int[20][20];

    // 숫자 채우기
    static void fill(int r, int c, int value) {
        // 범위
        if (r < 0 || r > N - 1 || c < 0 || c > N - 1) 
            return;
        // 경계선
        if (Mark[r][c] != 0)
            return;

        Mark[r][c] = value;
        //상,하,좌,우
        fill(r - 1, c, value);
        fill(r + 1, c, value);
        fill(r, c - 1, value);
        fill(r, c + 1, value);
    }

    static int solve() {
        int res = INF;

        // N-2 까지만 필요
        for (int x = 0; x < N - 2; x++) {

            // 1~N-1까지만 필요
            for (int y = 1; y < N - 1; y++) {

                // x + d1 < N - 1 => d2가 1일 경우가 있어서 N-1
                for (int d1 = 1; x + d1 < N - 1 && y - d1 >= 0; d1++) {
                    for (int d2 = 1; x + d1 + d2 < N && y + d2 < N; d2++) {

                        // 초기화
                        for (int i = 0; i < N; i++)
                            Arrays.fill(Mark[i], 0);

                        // 5번 경계선 만들기
                        for (int i = 0; i <= d1; i++) {
                            Mark[x + i][y - i] = 5;
                            Mark[x + d2 + i][y + d2 - i] = 5;
                        }
                        for (int i = 0; i <= d2; i++) {
                            Mark[x + i][y + i] = 5;
                            Mark[x + d1 + i][y - d1 + i] = 5;
                        }

                        // 1, 2, 3, 4 경계선 만들기
                        for (int r = x - 1; r >= 0; r--)
                            Mark[r][y] = 1;
                        for (int c = y + d2 + 1; c < N; c++)
                            Mark[x + d2][c] = 2;
                        for (int c = y - d1 - 1; c >= 0; c--)
                            Mark[x + d1][c] = 3;
                        for (int r = x + d1 + d2 + 1; r < N; r++)
                            Mark[r][y - d1 + d2] = 4;

                        // 각 꼭지점에서 시작하여 숫자 채우기
                        fill(0, 0, 1);
                        fill(0, N - 1, 2);
                        fill(N - 1, 0, 3);
                        fill(N - 1, N - 1, 4);

                        // 각 선거구 사람 구하기
                        int people[] = new int[6];
                        for (int r = 0; r < N; ++r)
                            for (int c = 0; c < N; ++c)
                                people[Mark[r][c]] += arr[r][c];

                        // 0, 5 번은 같은 구역이다.
                        people[5] += people[0];

                        // 최대 최소 구하기
                        int minP = INF, maxP = 0;
                        for (int i = 1; i <= 5; ++i) {
                            minP = Math.min(minP, people[i]);
                            maxP = Math.max(maxP, people[i]);
                        }

                        // 최대와 최소 차이의 최소값 구하기
                        res = Math.min(res, maxP - minP);
                    }
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        System.out.println(solve());
        sc.close();
    }
}