/ BOJ

BOJ_17779_게리맨더링2_JAVA

문제 : 게리맨더링2

링크 : BOJ_17779_게리맨더링

접근 방식

상당히 복잡해보이는 시뮬레이션 문제였고, 실제로도 꽤 복잡한 문제였다. x,y,d1,d2 4개에 대해 브루트포스로 모든 경우의 수를 따져봐야한다.

그 후 먼저 경계선을 그리고 경계선 안쪽을 5구역으로 채운다.

경계선과 그 안쪽을 처리했다면, 이제 주어진 조건대로 4분면을 나누면 된다.

그 후 각 경우의 수 별로 가장 많은 인원, 가장 적은 인원의 차를 구해서 그 최솟값을 저장한다.

모든 반복문이 돌고 난 후 최솟값을 출력한다.

소스 코드

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

public class Main {

	static int N, arr[][], loc[][];

	static int x, y, d1, d2, ans;

	static int[] answer;

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(in.readLine());
		arr = new int[N + 1][N + 1];
		loc = new int[N + 1][N + 1];
		StringTokenizer st;
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 1; j <= N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		ans = Integer.MAX_VALUE;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				for (int k = 1; k <= N; k++) {
					for (int l = 1; l <= N; l++) {
						loc = new int[N + 1][N + 1];
						x = i;
						y = j;
						d1 = k;
						d2 = l;

						if (x + d1 + d2 > N || y - d1 < 1 || y + d2 > N) {
							continue;
						}
						line();

//						System.out.println("======================");

						int temp = sum();
//						System.out.println(temp);
						ans = Math.min(ans, temp);


					}
				}
			}
		}

		System.out.println(ans);
	}

	static int sum() {
		answer= new int[6];
		int max = 0;
		int min = Integer.MAX_VALUE;
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				switch(loc[i][j]) {
				case 1:
					answer[1] += arr[i][j];
					break;
				case 2:
					answer[2] += arr[i][j];
					break;
				case 3:
					answer[3] += arr[i][j];
					break;
				case 4:
					answer[4] += arr[i][j];
					break;
				case 5:
					answer[5] += arr[i][j];
					break;
				}
			}
		}

		for(int i=1;i<6;i++) {
			max = Math.max(max, answer[i]);
			min = Math.min(min, answer[i]);
		}

		return max-min;

	}

	// 구역 나누기
	// 각 꼭짓점 :
	// 1. x,y
	// 2. x+d1, y-d1
	// 3. x+d2, y+d2
	// 4. x+d1+d2, y-d1+d2
	static void line() {
		int x1 = x;
		int y1 = y;

		loc[x+d2+d1][y+d2-d1] = 5;
		loc[x][y] = 5;
		loc[x+d1][y-d1] = 5;
		loc[x+d2][y+d2] = 5;

		// 5번 구역1
		while (x1 != x+d1 || y1 != y-d1) {
			x1++;
			y1--;
			loc[x1][y1] = 5;
		}
		x1 = x;
		y1 = y;
		// 5번 구역2
		while (x1 != x+d2 || y1 != y+d2) {

			x1++;
			y1++;
			loc[x1][y1] = 5;
		}
		x1 = x+d1;
		y1 = y-d1;
		// 5번 구역3
		while (x1 != x+d1+d2 || y1 != y-d1+d2) {
			x1++;
			y1++;
			loc[x1][y1] = 5;


		}

		x1 = x+d2;
		y1 = y+d2;
		// 5번 구역4
		while (x1 != x+d1+d2 || y1 != y-d1+d2) {

			x1++;
			y1--;
			loc[x1][y1] = 5;			
		}

		// 5번구역 내부 채우기
		for(int i=x+1;i<x+d1+d2;i++) {
			for(int j=1;j<=N;j++) {
				if(loc[i][j] == 5) {
					int k = j+1;
					while(loc[i][k] != 5) {
						loc[i][k] = 5;
						k++;
					}
					break;
				}
			}
		}

		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				if(loc[i][j] != 5) {
					if(i <= x+d1 && j <= y) {
						loc[i][j] = 1;
					}
					if(i <= x+d2 && j > y &&  j <= N) {
						loc[i][j] = 2;
					}
					if(i >= x+d1 && i <= N && j < y-d1+d2) {
						loc[i][j] = 3;
					}
					if(i > x+d2 && i <= N && j >= y-d1+d2 && j <= N) {
						loc[i][j] = 4;
					}
				}
			}
		}


//		for(int i=1;i<=N;i++) {
//			System.out.println(Arrays.toString(loc[i]));
//		}
	}

}

4중첩 반복문에 내부에서 반복문이 또 돌아가기 때문에 시간초과가 나지 않을까 걱정했는데, 다행히 통과가 잘 되었다.