[BOJ]17779: 게리맨더링 2

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

17779번: 게리맨더링 2

 

게리맨더링1은 그래프 개념을 통해 쉽게 구현할 수 있었는데 2번은 배열 빡구현이라 인덱스 설정하면서 두통을 얻을 수 있었다!

다 풀고 난 뒤 보니까 규칙을 사용하신 분들도 있었는데 난 복잡할 수록 조건에 맞게 단위를 나눠서 푸는게 편해서 빡구현 했다^^.

 

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. ▶︎ 범위에 해당하는 경우만 다음 단계를 진행한다. 
2. 다음 칸은 경계선이다. ▶︎ markFifthDistrict(int x, int y, int d1, int d2) 
3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다. ▶︎ markFifthInnerDistrict()
   1. district[r][c] == 5인 경우, c를 증가시키며 Stack에 넣는다.
   2. 만약 district[r][c] == 5인 경우, Stack의 값을 모두 pop하여 district[r][c]를 5로 표시한다.
4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호를 기준에 따라 나눈다. ▶︎ markDistrict(int x, int y, int d1, int d2)
5. 구역별 인구수를 구하여 현재까지의 최솟값과 비교한다. ▶︎ calcDistrictPopulation()  

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class p17779 {
	static int N;
	static int[][] A;
	static int[][] district;
	static int[] population;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		A = new int[N][N];

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int answer = Integer.MAX_VALUE;
		for (int x = 0; x < N; x++) {
			for (int y = 1; y < N - 1; y++) {
				for (int d1 = 1; d1 < N; d1++) {
					for (int d2 = 1; d2 < N; d2++) {
						// 1. 기준점과 경계의 길이를 정한다.
						if (x + d1 + d2 >= N || y - d1 < 0 || y + d2 >= N)
							continue;

						district = new int[N][N];
						// 2. 경계선을 표시한다.
						markFifthDistrict(x, y, d1, d2);
						// 3. 경계선 안의 선거구를 표시한다.
						markFifthInnerDistrict();
						// 4. 5번 선거구가 아닌 선거구를 표시한다.
						markDistrict(x, y, d1, d2);

						// 5. 선거구 인거수의 최소값을 구한다.
						int diff = calcDistrictPopulation();
						answer = Math.min(diff, answer);
					}
				}
			}
		}

		System.out.println(answer);
	}

	private static int calcDistrictPopulation() {
		Arrays.sort(population);
		return population[5] - population[1];
	}

	private static void markDistrict(int x, int y, int d1, int d2) {
		population = new int[6];

		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				if (district[r][c] == 5) {
					population[5] += A[r][c];
					continue;
				}
				if (r < x + d1 && c <= y)
					district[r][c] = 1;
				else if (r <= x + d2 && y < c)
					district[r][c] = 2;
				else if (x + d1 <= r && c < y - d1 + d2)
					district[r][c] = 3;
				else if (x + d2 < r && y - d1 + d2 <= c)
					district[r][c] = 4;
				population[district[r][c]] += A[r][c];
			}
		}
	}

	private static void markFifthInnerDistrict() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (district[i][j] == 5) {
					Stack<Integer> stack = new Stack<>();
					j++;
					while (j < N) {
						if (district[i][j] == 5) {
							while (!stack.isEmpty()) {
								district[i][stack.pop()] = 5;
							}
							break;
						}
						stack.add(j);
						j++;
					}
				}
			}
		}
	}

	private static void markFifthDistrict(int x, int y, int d1, int d2) {
		for (int d = 0; d <= d1; d++) {
			district[x + d][y - d] = 5;
		}
		for (int d = 0; d <= d2; d++) {
			district[x + d][y + d] = 5;
		}
		for (int d = 0; d <= d2; d++) {
			district[x + d1 + d][y - d1 + d] = 5;
		}
		for (int d = 0; d <= d1; d++) {
			district[x + d2 + d][y + d2 - d] = 5;
		}
	}

}