[BOJ] 17779 : 게리맨더링 2 - travelbeeee

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

---

[ 알고리즘풀이 ]

■ 처음엔 5번 선거구를 먼저 정하고, 남는 자리에 한해서 아래를 만족하면 1, 2, 3, 4번 선거구로 정하려고 했다. 그러면 5번 선거구만 정하고 나머지는 전체를 순회하며 단순 if 문 만으로 처리할 수 있기 때문에 구현이 깔끔할 것 같았다.

• 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

하지만, 5번 선거구를 먼저 선정하려면 다이아몬드를 그려야되는데 이 부분이 구현하기 어려워, 결국 1, 2, 3, 4 번 선거구를 정하고 남는 부분을 5번 선거구로 정했다.

■ 모든 x, y, d1, d2에 대해서 게임을 진행하고, 애초에 5개 구역으로 못나누는 경우는 return, 아니라면 선거구를 나누며 답을 갱신하면 된다.

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

int N, map[21][21] = {}, ans = INF;

void separate(int x, int y, int d1, int d2) {
	// 애초에 5개 구역으로 못나누는 경우.
	if (!(1 <= x && x + d1 + d2 <= N && 1 <= y - d1 && y + d2 <= N))
		return;

	int label[21][21] = {}, sum[5] = {};
	// 1구역
	for (int r = 1; r < x + d1; r++) {
		if (r < x)
			for (int c = 1; c <= y; c++)
				label[r][c] = 1;
		else
			for (int c = 1; c <= y - (r - x + 1); c++)
				label[r][c] = 1;
	}
	// 2구역
	for (int r = 1; r <= x + d2; r++) {
		if (r <= x)
			for (int c = y + 1; c <= N; c++)
				label[r][c] = 2;
		else
			for (int c = y + 1 + (r - x); c <= N; c++)
				label[r][c] = 2;
	}
	// 3구역
	for (int r = x + d1; r <= N; r++) {
		if (r < x + d1 + d2)
			for (int c = 1; c < y - d1 + (r - (x + d1)); c++)
				label[r][c] = 3;
		else
			for (int c = 1; c < y - d1 + d2; c++)
				label[r][c] = 3;
	}
	// 4구역
	for (int r = x + d2 + 1; r <= N; r++) {
		if (r <= x + d1 + d2)
			for (int c = y + d2 + 1 - (r - (x + d2)); c <= N; c++)
				label[r][c] = 4;
		else
			for (int c = y - d1 + d2; c <= N; c++)
				label[r][c] = 4;
	}
	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= N; c++)
			sum[label[r][c]] += map[r][c];

	sort(sum, sum + 5);
	ans = min(ans, sum[4] - sum[0]);
	return;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];

	
	// d1, d2, x, y 마다 게임을 진행하자.
	for (int d1 = 1; d1 <= N; d1++)
		for (int d2 = 1; d2 <= N; d2++)
			for (int x = 1; x <= N; x++)
				for (int y = 1; y <= N; y++)
					separate(x, y, d1, d2);
	
	cout << ans;
}

---