게리맨더링2 (17779)

1. 문제

문제 링크

설명
재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

선거구를 나누는 방법은 다음과 같다.

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
2. 다음 칸은 경계선이다.

• (x, y), (x+1, y-1), ..., (x+d1, y-d1)
• (x, y), (x+1, y+1), ..., (x+d2, y+d2)
• (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
• (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.

• 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
• 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
• 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
• 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

아래는 크기가 7×7인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

x = 2, y = 4, d1 = 2, d2 = 2

구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

입력
첫째 줄에 재현시의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 A[r][c]를 의미한다.

출력
첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.

2. 풀이

한 좌표에 대해서 선거구를 나눌 4개의 꼭지점을 구하고
그 꼭지점에 대해서 나뉘어진 선거구의 인구의 합을 구하는 문제입니다.
구현 난이도가 조금 있으니 하나씩 차근차근 계획을 세웁시다.

계획1 - 4개의 꼭지점을 구합니다.

조건이 복잡해보여도 단순화시켜 꼭지점의 정의를 구해보면 이와 같습니다.

꼭지점1 - (x, y)
꼭지점2 - (x + d1, y - d1)
꼭지점3 - (x + d2, y + d2)
꼭지점4 - (x + d1 + d2, y + d2 - d1)

계획2 - 4개의 꼭지점으로부터 선거구를 나눕니다.

N = 5, x = 2, y = 2, d1 = 1, d2 = 1일 때 예를 들어보겠습니다.

처음엔 전 지역을 5번 선거구로 초기화 합니다.

5 5 5 5 5
5 5 5 5 5
5 5 5 5 5
5 5 5 5 5
5 5 5 5 5

4개의 꼭지점을 찍습니다.

5 5 5 5 5
5 5 X 5 5
5 X 5 X 5
5 5 X 5 5
5 5 5 5 5

꼭지점으로부터 선거구를 나눕니다.

1 1 1 2 2
1 1 X 2 2
3 X 5 X 2
3 3 X 4 4
3 3 4 4 4

여기서 주의한 점은 X표시한 꼭지점 부분도 5번 선거구입니다.

계획3 - d1과 d2의 범위를 구합니다.

눈치챈 분들도 있겠지만
d1은 현 좌표에서 왼쪽 대각선 아래로 얼만큼 갈 수 있는지,
d2는 현 좌표에서 오른쪽 대각선 아래로 얼만큼 갈 수 있는지를 나타냅니다.
그렇다면 y좌표(가로 방향) 기준으로
d1은 1 ~ y까지의 범위를 가질 수 있고
d2는 1 ~ N - y - 1까지의 범위를 가질 수 있습니다.

여기까진 괜찮습니다만, 맨 아래의 꼭지점은 범위를 벗어날 수 있기 때문에
별도의 예외 처리가 필요합니다.

계획4 - 선거구를 나누는 모든 경우에 대해 완전 탐색을 합니다.

어려운 부분은 끝났습니다.
이제 전체 코드를 통해 실제로 구현해보겠습니다.

3. 전체 코드

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

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws Exception {
		int N = Integer.parseInt(br.readLine());
		int[][] divide = new int[N][N];
		int[][] A = new int[N][N];
		int[] area = new int[5];

		for (int i = 0; i < N; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				A[i][j] = Integer.parseInt(stk.nextToken());
				divide[i][j] = 4; // 기본 5번 선거구로 초기화
			}
		}
		
		int ans = 987654321;
		
		for (int x1 = 0; x1 < N; x1++) {
			for (int y1 = 1; y1 < N; y1++) {
				// d1과 d2의 범위는 y좌표에 종속됩니다.
				for (int d1 = 1; d1 <= y1; d1++) {
					for (int d2 = 1; d2 < N - y1; d2++) {
						// 맨 아래의 꼭지점이 범위를 벗어날 때 예외 처리
						int x4 = x1 + d1 + d2;
						int y4 = y1 + d2 - d1;
						
						if (x4 < 0 || x4 >= N || y4 < 0 || y4 >= N) continue;
						
						// 2개의 꼭지점을 추가적으로 구해줍니다.
						int x2 = x1 + d1;
						int x3 = x1 + d2;
						
						// 4개의 꼭지점으로부터 선거구를 나눕니다.
						int adjust = 0;
						
						// 1번 선거구
						for (int i = 0; i < x2; i++) {
							// 첫 번째 꼭지점보다 크거나 같을 때부터 조정하기
							if (i >= x1) adjust++;
							
							for (int j = 0; j <= y1 - adjust; j++) {
								divide[i][j] = 0;
							}
						}
						
						adjust = 0;
						
						// 2번 선거구
						for (int i = 0; i <= x3; i++) {
							// 첫 번째 꼭지점보다 클 때부터 조정하기
							if (i > x1) adjust++;
							
							for (int j = y1 + 1 + adjust; j < N; j++) {
								divide[i][j] = 1;
							}
						}
						
						adjust = 0;
						
						// 3번 선거구
						for (int i = N - 1; i >= x2; i--) {
							// 네 번째 꼭지점보다 작아질 때부터 조정하기
							if (i < x4) adjust++;
							
							for (int j = 0; j < y4 - adjust; j++) {
								divide[i][j] = 2;
							}
						}
						
						adjust = 0;
						
						// 4번 선거구
						for (int i = N - 1; i > x3; i--) {
							// 네 번째 꼭지점보다 작거나 같을 때부터 조정하기
							if (i <= x4) adjust++;
							
							for (int j = y4 + adjust; j < N; j++) {
								divide[i][j] = 3;
							}
						}
						
						// 나눈 선거구의 인구 총합 구하기
						for (int i = 0; i < N; i++) {
							for (int j = 0; j < N; j++) {
								area[divide[i][j]] += A[i][j];
								divide[i][j] = 4; // 선거구는 다시 기본 5번 선거구로 초기화
							}
						}
						
						Arrays.sort(area);
						ans = Math.min(ans, area[4] - area[0]);
						Arrays.fill(area, 0);
					}
				}
			}
		}

		bw.write(ans + "");
		bw.close();
	}
}