[백준/BOJ] 백준 17779번 : 게리맨더링 2

www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

가능한 기준점의 가능한 경계의 길이를 모두 고려하여 각 선거구 표시를 해두는 방식으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

int n;
int board[101][101];

//기준점에서 가능한 경계의 길이를 모두 고려한다
int Solve(pair<int, int> point)
{
	int ret = 987654321;
	for (int d1 = 1; d1 <= n; d1++)
	{
		for (int d2 = 1; d2 <= n; d2++)
		{
			vector<vector<int>> check_board(n + 1, vector<int>(n + 1, 0));
			vector<int> num(6, 0); //각각 선거구의 인구 저장
			int max_num;
			int min_num;

			if (point.first + d1 + d2 <= n && 1 <= point.second - d1 && point.second + d2 <= n)
			{
				//5번 선거구
				for (int i = 0; i <= d1; i++)
					check_board[point.first + i][point.second - i] = 5;
				for (int i = 0; i <= d2; i++)
					check_board[point.first + i][point.second + i] = 5;
				for (int i = 0; i <= d2; i++)
					check_board[point.first + d1 + i][point.second - d1 + i] = 5;
				for (int i = 0; i <= d1; i++)
					check_board[point.first + d2 + i][point.second + d2 - i] = 5;


				queue<pair<int, int>> q;
				int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

				q.push(make_pair(point.first + 1, point.second));
				check_board[point.first + 1][point.second] = 5;

				while (!q.empty())
				{
					pair<int, int> here = q.front();
					q.pop();

					for (int i = 0; i < 4; i++)
					{
						pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

						if (check_board[there.first][there.second] == 0)
						{
							check_board[there.first][there.second] = 5;
							q.push(there);
						}
					}

				}

				if (d1 == 1)
				{
					for (int i = 0; i < d2; i++)
						check_board[point.first + 1 + i][point.second + i] = 5;
				}

				if (d2 == 1)
				{
					for (int i = 0; i < d1; i++)
						check_board[point.first + 1 + i][point.second - i] = 5;
				}

				for (int i = 1; i < point.first + d1; i++)
					for (int j = 1; j <= point.second; j++)
						if (check_board[i][j] != 5)
							check_board[i][j] = 1;

				for (int i = 1; i <= point.first + d2; i++)
					for (int j = point.second + 1; j <= n; j++)
						if (check_board[i][j] != 5)
							check_board[i][j] = 2;

				for (int i = point.first + d1; i <= n; i++)
					for (int j = 1; j < point.second - d1 + d2; j++)
						if (check_board[i][j] != 5)
							check_board[i][j] = 3;

				for (int i = point.first + d2 + 1; i <= n; i++)
					for (int j = point.second - d1 + d2; j <= n; j++)
						if (check_board[i][j] != 5)
							check_board[i][j] = 4;

				for (int i = 1; i <= n; i++)
					for (int j = 1; j <= n; j++)
					{
						num[check_board[i][j]] += board[i][j]; //선거구에 맞는 인원 저장
					}

				max_num = max(max(num[1], num[2]), max(num[3], num[4]));
				max_num = max(max_num, num[5]);

				min_num = min(min(num[1], num[2]), min(num[3], num[4]));
				min_num = min(min_num, num[5]);

				ret = min(ret, max_num - min_num);
			}
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int result = 987654321;
	cin >> n;

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			result = min(result, Solve(make_pair(i, j)));

	cout << result;

}