백준 17779 : 게리맨더링 2

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

17779번: 게리맨더링 2

[ 문제풀이 ]

N의 범위가 작기 때문에 가능한 x, y, d1, d2 경우를 모두 구해서 최솟값을 구하면 되는 문제이다.

전체를 5구간으로 먼저 채워놓고 1, 2, 3, 4 구간을 업데이트해주는 식으로 구현하면 조금 더 쉽게 구현할 수 있다.

각 구간마다 경계선 안쪽으로 가는 구간만 조심해서 범위를 지정해 주면 쉽게 해결할 수 있을 것이다.

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

public class Main {

	static int N, answer;
	static int[][] map, temp;
	static int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		answer = Integer.MAX_VALUE;
		map = new int[N+1][N+1];
		temp = new int[N+1][N+1];
		for (int i = 1; i <= N; ++i) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; ++j) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int x = 1; x <= N; ++x) {
			for (int y = 1; y <= N; ++y) {
				for (int d1 = 1; d1 <= y; ++d1) {
					for (int d2 = 1; d2 < N - y; ++d2) {
						if (isValid(x, y, d1, d2)) {
							solve(x, y, d1, d2);
						}
					}
				}
			}
		}
		bw.write(answer + "\n");
		bw.flush();bw.close();br.close();
	}
	
	//경계선이 범위를 벗어나는지 확인
	public static boolean isValid(int x, int y, int d1, int d2) {
		if (x + d1 > N || y - d1 < 1) return false;
		if (x + d2 > N || y + d2 > N) return false;
		if (x + d1 + d2 > N || y - d1 + d2 > N || y + d2 - d1 < 1) return false;
		return true;
	}

	public static void solve(int x, int y, int d1, int d2) {
		int[] cnt = new int[5];

		//전체 영역을 5로 채움
		for (int i = 1; i <= N; ++i) Arrays.fill(temp[i], 5);

		//1번 영역
		for (int r = 1, k = y; r < x + d1; ++r) {
			for (int c = 1; c <= y; ++c) {
				if (r >= x) {
					if (c >= k) {
						if (c == k) k--;
						continue;
					}
				}
				temp[r][c] = 1;
			}
		}

		//2번 영역
		for (int r = 1, k = x + 1, h = 0; r <= x + d2; ++r) {
			for (int c = y + 1 + h; c <= N; ++c) {
				if (r == k) {
					k++; h++;
					continue;
				}
				temp[r][c] = 2;
			}
		}

		//3번 영역
		for (int r = N, k = x + d1 + d2 - 1, h = 0; r >= x + d1; --r) {
			for (int c = y - d1 + d2 - 1 + h; c >= 1; --c) {
				if (r == k) {
					k--; h--;
					continue;
				}
				temp[r][c] = 3;
			}
		}
		
		//4번 영역
		for (int r = N, k = x + d2 + d1, h = 0; r > x + d2; --r) {
			for (int c = y - d1 + d2 + h; c <= N; ++c) {
				if (r == k) {
					k--; h++;
					continue;
				}
				temp[r][c] = 4;
			}
		}

		for (int i = 1; i <= N; ++i) {
			for (int j = 1; j <= N; ++j) {
				cnt[temp[i][j] - 1] += map[i][j];
			}
		}
		
		Arrays.sort(cnt);
		answer = Math.min(answer, cnt[4] - cnt[0]);
	}
}