백준 게리맨더링 2 재풀이

완전 탐색으로 간단히 풀 수 있었다.

#include<iostream>


using namespace std;


int N;
int arr[21][21];

int main(void)
{
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> arr[i][j];
		}
	}
	int mina = 987654321;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			for (int d1 = 1; d1 <= N; d1++)
			{
				for (int d2 = 1; d2 <= N; d2++)
				{
					if (1 <= i && i < i + d1 + d2 && i + d1 + d2 <= N && 1 <= j - d1 && j - d1 < j && j < j + d2 && j + d2 <= N)
					{
						int area[21][21];
						for (int i = 1; i <= N; i++)
						{
							for (int j = 1; j <= N; j++)
							{
								area[i][j] = 0;
							}
						}

						int r = i;
						int c = j;
						while (r <= i + d1 && c >= j - d1)
						{
							area[r][c] = 5;
							r++;
							c--;
						}

						r = i;
						c = j;
						while (r <= i + d2 && c <= j + d2)
						{
							area[r][c] = 5;
							r++;
							c++;
						}

						r = i + d1;
						c = j - d1;
						while (r <= i + d1 + d2 && c <= j - d1 + d2)
						{
							area[r][c] = 5;
							r++;
							c++;
						}

						r = i + d2;
						c = j + d2;
						while (r <= i + d2 + d1 && c >= j + d2 - d1)
						{
							area[r][c] = 5;
							r++;
							c--;
						}
						

						
						for (int r = 1; r < i + d1; r++)
						{
							for (int c = 1; c <= j; c++)
							{
								if (area[r][c] == 5)
								{
									break;
								}
								area[r][c] = 1;
							}
						}

						for (int r = 1; r <= i + d2; r++)
						{
							for (int c = N; c >= j+1; c--)
							{
								if (area[r][c] == 5)
								{
									break;
								}
								area[r][c] = 2;
							}
						}

						for (int r = i + d1; r <= N; r++)
						{
							for (int c = 1; c < j - d1 + d2; c++)
							{
								if (area[r][c] == 5)
								{
									break;
								}
								area[r][c] = 3;
							}
						}

						for (int r = i + d2 + 1; r <= N; r++)
						{
							for (int c = N; c >= j -d1 +d2; c--)
							{
								if (area[r][c] == 5)
								{
									break;
								}
								area[r][c] = 4;
							}
						}
						
						int count[6];
						for (int k = 1; k <= 5; k++)
						{
							count[k] = 0;
						}
						
						for (int r = 1; r <= N; r++)
						{
							for (int c = 1; c <= N; c++)
							{
								if (area[r][c] == 1)
								{
									count[1] += arr[r][c];
								}
								else if (area[r][c] == 2)
								{
									count[2] += arr[r][c];
								}
								else if (area[r][c] == 3)
								{
									count[3] += arr[r][c];
								}
								else if (area[r][c] == 4)
								{
									count[4] += arr[r][c];
								}
								else if (area[r][c] == 5 || area[r][c] == 0)
								{
									count[5] += arr[r][c];
								}
							}
						}
					
						int maxb = 0;
						int minb = 987654321;
						for (int k = 1; k <= 5; k++)
						{
							if (maxb < count[k])
							{
								maxb = count[k];
							}

							if (minb > count[k])
							{
								minb = count[k];
							}
						}


						if (mina > maxb - minb)
						{
							mina = maxb - minb;
						}
						
					}
				}
			}
		}
	}
	cout << mina << endl;


}