[백준 17779] 게리맨더링 2 (C++)

문제 링크: https://www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

1. 주의할 점

- 각 구역을 어떤 방식으로 나눌건지 잘 계산한다

- 브루트포스를 통해 경우의 수 전부 구해본다

 

2. 구현

- 각 인구를 입력 받으면서 배열에서의 총합을 따로 구한다

- D1, D2의 최소 길이가 1인 것을 감안하여 DFS를 수행한다

- DFS를 수행하며 각 변이 범위밖으로 넘어가지 않는다면 브루트포스 함수인 Start()를 수행한다

- 1~4 구역까지 인구수 전부 구한 후, 5구역은 전체 인구수에서 1~4구역을 합한만큼 빼서 구한다

- 각 지역의 최고 인구수와 최소 인구수의 차이를 구하여 Result와 비교한다

 

#define MAX 987654321
#include <iostream>
#include <algorithm>
using namespace std;

int arr[20][20],dup[20][20];
int num, result = MAX, tot = 0;
int pop[6];

void start(int y, int x, int d1, int d2) {
	for (int i = 1; i < 6; i++)
		pop[i] = 0;
	int maxi = 0, mini = MAX;
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++)
			dup[i][j] = 5;
	
	//1구역
	for (int i = 0; i < y; i++) {
		for (int j = 0; j <= x+d1; j++) {
			if (x + y == i + j) break;
			else {
				dup[i][j] = 1;
				pop[1] += arr[i][j];
			}
		}
	}
	//2구역
	for (int i = 0; i <= y+d2-d1; i++) {
		for (int j = x+d1+1; j < num; j++) {
			if (i - j >= y - x - 2 * d1) continue;
			else {
				dup[i][j] = 2;
				pop[2] += arr[i][j];
			}
		}
	}
	//3구역	
	for (int i = y; i <num; i++) {
		for (int j = 0; j < x+d2; j++) {
			if (i - j == y - x) break;
			else {
				dup[i][j] = 3;
				pop[3] += arr[i][j];
			}
		}
	}

	//4구역
	for (int i = y + d2-d1+1; i <num; i++) {
		for (int j = x+d2; j < num; j++) {
			if (i + j <= x + y + 2 * d2) continue;
			else {
				dup[i][j] = 4;
				pop[4] += arr[i][j];
			}
		}
	}
	pop[5] = tot - (pop[1] + pop[2] + pop[3] + pop[4]);
	for (int i = 1; i < 6; i++) {
		maxi = max(maxi, pop[i]);
		mini = min(mini, pop[i]);
	}	
	result = min(result, maxi - mini);
}

void dfs(int y, int x) {
	for (int i = 1; i < num; i++) {				//d1
		for (int j = 1; j < num; j++) {			//d2
			if (y - i >= 0 && y + j < num && x + i + j < num)
				start(y, x, i, j);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num;
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++) {
			cin >> arr[i][j];
			tot += arr[i][j];
		}

	for(int i=1;i<num-1;i++)
		for (int j = 0; j < num - 2; j++) {
			dfs(i, j);
		}
	cout << result;
	return 0;
}