[백준] 게리맨더링2 17779번 C++ 풀이

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

17779번: 게리맨더링 2

#include <iostream>
#include <algorithm>
using namespace std;
int arr[21][21];
int area[21][21];
int population[5];
int N;
int res = 987654321;
void FindRes()
{
	for(int i=1;i<=N;i++)
		for (int j = 1; j <= N; j++)
			population[area[i][j]-1] += arr[i][j];

	sort(population, population + 5);
	res = min(res, population[4] - population[0]);
}

void MakeArea(int x,int y, int D1, int D2)
{
	for(int i=1;i<x+D1;i++)
		for (int j = 1; j <= y; j++)
		{
			if (area[i][j] == 5)
				continue;
			area[i][j] = 1;
		}

	for(int i=1;i<=x+D2;i++)
		for (int j = y + 1; j <= N; j++)
		{
			if (area[i][j] == 5)
				continue;
			area[i][j] = 2;
		}

	for(int i=x+D1;i<=N;i++)
		for (int j = 1; j < y - D1 + D2; j++)
		{
			if (area[i][j] == 5)
				continue;
			area[i][j]=3;
		}

	for(int i=x+D2+1;i<=N;i++)
		for (int j = y - D1 + D2; j <= N; j++)
		{
			if (area[i][j] == 5)
				continue;
			area[i][j] = 4;
		}

}

void FiveArea(int x,int y,int D1,int D2)
{
			

		for (int i = 0; i <= D1; i++)
		{
			area[x + i][y - i] = 5; // 1
			area[x + D2 + i][y + D2 -i] = 5; // 4
		}

		for (int i = 0; i <= D2; i++)
		{
			area[x + i][y + i] = 5; // 2
			area[x + D1 + i][y - D1 + i] = 5; // 3
		}

		for (int i = 0; i < D1; i++) {
			int t = 1;
			while (area[x + i + t][y - i] != 5) {
				area[x + i + t][y - i] = 5;
				t++;
			}
		}

		for (int i = 0; i < D2; i++) {
			int t = 1;
			while (area[x + i + t][y + i] != 5) {
				area[x + i + t][y + i] = 5;
				t++;
			}
		}



}
bool Able(int i, int j, int D1, int D2)
{
	if (i + D1 > N || j - D1 <= 0)
		return false;
	if (i + D2 > N || j + D2 > N)
		return false;
	if (i + D1 + D2 > N || j - D1 + D2 > N)
		return false;
	if (i + D2 + D1 > N || j + D2 - D1 <= 0)
		return false;
	return true;
}

void solve()
{
	for (int i = 1; i <= N; i++) 
	{
		for (int j = 1; j <= N; j++)
		{
			for (int D1 = 1; D1 < j; D1++) 
			{
				for (int D2 = 1; D2 <= N - j; D2++)
				{
					if (Able(i, j, D1, D2))
					{
						for (int i = 1; i <= N; i++)
							for (int j = 1; j <= N; j++)
								area[i][j] = 0;
						for (int i = 0; i < 5; i++)
							population[i] = 0;

						FiveArea(i,j,D1, D2);
						MakeArea(i,j,D1,D2);
						FindRes();
					}
				}
			}
		}
	}

}

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

 

기준점 x, y로부터 d1,d2 만큼 이동하는 것입니다.

경계선을 봅시다

1,2,3,4에 밑줄을 쳐뒀는데 각 방법별로 이동경로입니다.

1번 방법을 보시면 (x,y) 기준점에서 시작하여 (x+d1,y-d1)까지 경계선을 그립니다

또 여기서 3번 방법으로 이어지는데 (x+d1,y-d1)부터 (x+d1+d2,y-d1+d2)로 그려집니다

 

기준점 x,y로부터 도착지점까지 범위가 배열안의 범위에 포함이 된다면 이것은 영역을 나눌 수 있는, 답의 후보가 될 수 있는 경계선을 그릴 수 있다는 뜻입니다.

bool Able(int i, int j, int D1, int D2)
{
	if (i + D1 > N || j - D1 <= 0) // 1로 이동이 불가능?
		return false;
	if (i + D2 > N || j + D2 > N) // 2로 이동이 불가능?
		return false;
	if (i + D1 + D2 > N || j - D1 + D2 > N) // 3로 이동이 불가능 ?
		return false;
	if (i + D2 + D1 > N || j + D2 - D1 <= 0) // 4
		return false;
	return true; //모두 해당하지 않으므로 가능
}

 

만약 Able 함수에서 가능하다고 판명이난다면 

FiveArea(i,j,D1, D2);
MakeArea(i,j,D1,D2);
FindRes();

5번 선거구(FiveArea)를 그리고 나머지 선거구(MakeArea)를 그려줍니다.

그리고 선거구를 통해 최댓값과 최솟값의 차이를 구합니다.

1,2,3,4번 방법을 통해 경계선을 5번 선거구 경계선을 초기화 시켜줍니다.

경계선을 그리는 1~4번 방법

5번 선거구의 경계선 내용도 5로 초기화 시켜줍니다

빨간색으로 선을 그어놓은 것이 가상의 경계선이라고 생각하시고 보세요~

첫 for문은 1번 방법으로 5번 경계선 아래로 채워주는 코드이고

두 번째 for문은 2번 방법으로 5번 경계선 아래로 5로 초기화 시켜주는 코드입니다.

while문을 통해 5번 경계선을 만날 때까지 내려가며 채워주는 코드입니다.

D1,D2를 이용해서 채워줍니다.

 

MakeArea 함수는 아래의 조건을 통해 초기화를 시켜주면 됩니다.

마무리로 모든 배열 영역을 돌면서 해당하는 선거구에 인구수를 더해주고

정렬을 시켜 최대와 최소의 차를 구해 현재까지의 결과 res 보다 작다면 갱신해주면 됩니다.

void FindRes()
{
	for(int i=1;i<=N;i++)
		for (int j = 1; j <= N; j++)
			population[area[i][j]-1] += arr[i][j];

	sort(population, population + 5);
	res = min(res, population[4] - population[0]);
}

 

아래 코드처럼 해도 무관합니다.

			for (int D1 = 1; D1 <=N; D1++) 
			{
				for (int D2 = 1; D2 <= N; D2++)