백준 17779번: 게리맨더링 2

문제 설명

• https://www.acmicpc.net/problem/17779
• 2차원 배열을 정해진 방법으로 나누는 문제입니다.

접근법

• 5번 구역을 먼저 찾는 방식으로 문제를 풀었습니다.
  • 5번 구역은 d1과 d2의 크기차이에 따라 다음 두 가지 모양이 나옵니다. (d1과d2가 같은 경우는 특별한 처리가 필요 없습니다)
    • 
  • 두 도형 모두 x값을 기준으로 3가지 구간을 가집니다.
    • x부터 x+Math.min(d1,d2)까지
    • x+Math.min(d1,d2)부터 x+Math.min(d1,d2)까지
    • x+Math.min(d1,d2)부터 x+d1+d2까지
    • 
  • 각 구간에 따라 y의 값이 다음과 같이 변합니다.
    • 1번구간: (y - cnt)부터 (y + cnt)까지
    • 3번구간: (y + cnt - 2 d1)부터 (y - cnt + 2 d2)까지
    • 2번구간: 모향에 따라 다름
• 나머지 구역을 채울 때 다음을 유의해야 합니다.
  • 2차원 배열 범위로 하기 때문에 다음과 같은 오류영역이 생깁니다.
    • 
  • 이를 해결하기 위해 다음의 조건이 필요합니다.
    • 1번영역은 r+c<x+y라는 조건이 필요합니다.
      • x+y인 이유는 회색과 파란색의 경계값이 항상 x+y이기 때문입니다.
    • 2번영역은 r-c<x-y라는 조건이 필요합니다.
      • x-y인 이유는 회색과 파란색의 경계값이 항상 x-y이기 때문입니다.

정답

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int[][] board;
	static int MinVal = Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		board = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = sc.nextInt();
			}
		}
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				for (int d1 = 1; d1 <= N - 1; d1++) {
					for (int d2 = 1; d2 <= N - 1; d2++) {
						if (Validate(i, j, d1, d2)) {
							MinVal = Math.min(MinVal, Divide(i,j,d1,d2));
						}
					}
				}

			}
		}
		System.out.println(MinVal);

	}

	public static boolean Validate(int x, int y, int d1, int d2) {
		if (x + d1 + d2 < N && y - d1 >= 0 && y + d2 < N)
			return true;
		return false;
	}

	public static int Divide(int x, int y, int d1, int d2) {
		int Score1 = 0;
		int Score2 = 0;
		int Score3 = 0;
		int Score4 = 0;
		int Score5 = 0;
		int cnt = 0;
		int[][] board2 = new int[N][N];
		for (int i = x; i <= x + d1 + d2; i++) {
			if (cnt <= Math.min(d1, d2)) {
				for (int j = y - cnt; j <= y + cnt; j++) {
					Score5+= board[i][j];
					board2[i][j] = 5;
				}
			} else if (cnt >= Math.max(d1, d2)) {
					for (int j = y + cnt - 2 * d1; j <= y - cnt + 2 * d2; j++) {
						Score5+= board[i][j];
						board2[i][j] = 5;
					}

			} else {
				if (d1 > d2) {
					for (int j = y - cnt; j <= y + d2 - cnt + 1; j++) {
						Score5+= board[i][j];
						board2[i][j] = 5;
					}
				} else {
					for (int j = y +cnt - 2*d1; j <= y + cnt; j++) {
						Score5+= board[i][j];
						board2[i][j] = 5;
					}

				}
			}
			cnt++;
		}

		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {

				if (0 <= r && r <= x + d1 - 1 && 0 <= c && c <= y && board2[r][c] != 5 && r+c<x+y) {
					Score1+= board[r][c];
					board2[r][c] = 1;
				} 
				else if (0 <= r && r <= x + d2 && y < c && c <= N - 1 && board2[r][c] != 5 && r-c<x-y) {
					Score2+= board[r][c];
					board2[r][c] = 2;
				} 
				else if (x + d1 - 1 <= r && r <= N - 1 && 0 <= c && c <= y - d1 + d2 - 1 && board2[r][c] != 5) {
					Score3+= board[r][c];
					board2[r][c] = 3;
				} 
				else if (x + d2 < r && r <= N - 1 && y - d1 + d2 <= c && c <= N - 1 && board2[r][c] != 5) {
					Score4+= board[r][c];
					board2[r][c] = 4;
				}

			}
		}
        // 배열 확인을 위한 출력
//		System.out.println(x+"||"+y+"||"+d1+"||"+d2);
//		for (int j = 0; j < N; j++) {
//			System.out.println(Arrays.toString(board2[j]));
//		}
		// 최댓값 및 최솟값 찾기
		int MaxVal = Math.max(Math.max(Math.max(Score1, Score2), Math.max(Score3, Score4)),Score5);
		int MinVal = Math.min(Math.min(Math.min(Score1, Score2), Math.min(Score3, Score4)),Score5);
		return MaxVal-MinVal;
	}
}