[백준] 게리맨더링 2 17779 [Java]

출처 : www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

문제

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

재현시는 크기가 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. 다음 칸은 경계선이다.
   1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   4. (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인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

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

입력

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

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

출력

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

제한

• 5 ≤ N ≤ 20
• 1 ≤ A[r][c] ≤ 100

풀이 방법 

 - 완전 탐색 + 시뮬레이션 

 - 처음 문제를 접했을 땐, 어려워서 1시간 동안 문제만 바라보고 이해 하려고 했다.

 - 하지만 다 풀고 보니, 그냥 하란대로 하면 되는 것같다. ( 허무 하지만 막상 코드 구현 하기에는 어렵다. ㅠ ) 

1. x, y 를 처음부터 모두 탐색하며 d1, d2 또한 1부터 N 까지 4중 for문을 통해 완전탐색 
2. 4가지 큰 외곽 점의 범위가 map ( N ) 의 크기가 넘어가지 않다면, 5 구역의 경계 체크하기.
3. 5 구역을 기점으로 각 5개 구역의 최대값 - 최소값을 지속적으로 갱신한다.

코드

package 알고리즘스터디문제;

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

public class 게리맨더링2_17779 {
	// 왼 아래 , 오 아래 , 오른쪽 위로
	static int[][] dr = { { 1, -1 }, { 1, 1 }};
	static int N;
	static int[][] A;
	static int[][] map;
	static int min = Integer.MAX_VALUE;
	static int sum5= 0;
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		map = new int[N + 1][N + 1];

		int cnt = 0;

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

		// x, y 1부터 시작
		// d1, d2 조건에 맞도록 계속 증가시키면서
		for (int x = 1; x <= N; x++) {
			for (int y = 1; y <= N; y++) {
				for (int d1 = 1; d1 <= N; d1++) {
					if (x + d1 >= N)
						break; // 조기 탈출

					for (int d2 = 1; d2 <= N; d2++) {

						// 4중 for 문에서 각 조건에 따른 1) 선거구 구분 2) 해당 선거구역의 인구 구하기

						// 만약 각 변수가 각 조건에 해당 한다면
						if (isCnd(x, y, d1, d2)) {
							// 5 체크하고
							min = Math.min(solution(x, y, d1, d2), min);
							// 해당 함수에서 각 선거구 합 구하자
							
						}
					}
				}
			}
		}

		System.out.println(min);
	}

	private static int solution(int x, int y, int d1, int d2) {
		// TODO Auto-generated method stub
		boolean[][] isArea5 = new boolean[map.length + 1][map.length + 1];
		// 5 경계선 그리기
		for (int d = 0; d < d1 + 1; d++) {
			int nr = x + dr[0][0] * d;
			int nc = y + dr[0][1] * d;
			isArea5[nr][nc] = true;
		}
		// 맨 위에서 오른 아래쪽으로
		for (int d = 0; d < d2 + 1; d++) {
			int nr = x + dr[1][0] * d;
			int nc = y + dr[1][1] * d;
			isArea5[nr][nc] = true;
		}
		// 왼아래에서 시작 해서 오른아래로
		for (int d = 0; d < d2 + 1; d++) {
			int nr = x + d1 + dr[1][0] * d;
			int nc = y - d1 + dr[1][1] * d;
			isArea5[nr][nc] = true;
		}
		// 오른쪽 아래에서 시작으로 왼쪽아래로
		for (int d = 0; d < d1 + 1; d++) {
			int nr = x + d2 + dr[0][0] * d;
			int nc = y + d2 + dr[0][1] * d;
			isArea5[nr][nc] = true;
		}
		
		// 1구역의 합 구하기 , (1,1)
		int sum[] = new int[5];
		int sumother =0;
		int idx = 0;

		for (int i = 1; i < x + d1; i++) {
			for (int j = 1; j <= y; j++) {
				if (isArea5[i][j])
					break; // 개행
				sum[idx] += map[i][j];
			}
		}
		sumother += sum[idx];
		// 2구역의 합 구하기 1,N)
		idx++;
		for (int i = 1; i <= x + d2; i++) {
			for (int j = N; j > y; j--) {
				if (isArea5[i][j])
					break; // 개행
				sum[idx] += map[i][j];
			}
		}
		sumother += sum[idx];
		// 3구역의 합 구하기 N,1
		idx++;
		for (int i = N; i >= x + d1; i--) {
			for (int j = 1; j < y - d1 + d2; j++) {
				if (isArea5[i][j])
					break; // 개행
				sum[idx] += map[i][j];
			}
		}
		sumother += sum[idx];
		// 4구역 N,N 시작
		
		idx++;
		for (int i = N; i > x + d2; i--) {
			for (int j = N; j >= y - d1 + d2; j--) {
				if (isArea5[i][j])
					break; // 개행
				sum[idx] += map[i][j];
			}
		}
		sumother += sum[idx];
		// 5구역
		idx ++;
		sum[idx] = sum5 - sumother;
		
		
		Arrays.sort(sum);
		int result = sum[4] -sum[0];
		return result;
	}

	private static boolean isCnd(int x, int y, int d1, int d2) {
		// TODO Auto-generated method stub
		if (x + d1 <= N && y - d1 > 0 && x + d2 <= N && y + d2 <= N && x + d1 + d2 <= N && y - d1 + d2 <= N)
			return true;

		return false;
	}

}