백준 17779 게리맨더링 2 [Simulation + BruteForce]

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

17779번: 게리맨더링 2

문제 풀이

처음에는 문제가 간단하면서도 복잡하다는 생각이 들어서, 예제를 따라 그리다 보니까 문제가 이해가 됐습니다.

(문제 이해가 빠르면 더 시간을 단축할 수도!)

 

가장 중요한 것은 (x, y, d1, d2)를 정하는 것입니다.

정하고 나서 제5구역을 미리 먼저 만들고, 나머지 1 ~ 4 구역을 문제에서 제시한 범위에 따라 그려줍니다.

다 그려줬다면,

각 구역에 따라 합을 계산해서 "가장 큰 구역의 합 - 가장 작은 구역의 합"이 최소가 되는 것을 찾아주면 됩니다.

 

중간에 어려웠던 점은, 함수화 하는 방법(어떻게 하면 반복되는 코드들을 줄일 수 있을지?) 고민이 많았고..

경계선을 5로 색칠했을 때, 그 경계선 안쪽도 5로 칠해줘야 하는데 어떻게 색칠을 해줄까? 를 고민했습니다.

 

첫 번째 고민은 5구역을 색칠할 때, x와 y가 동시에 1씩 증가하면 true, true로 매개변수를 줘서 해결했고

x만 증가할 때는 true , false로 구분해서 색칠했습니다. ColoringFive 함수

 

두 번째 고민은 어떤 한 점(x, y)에서 상하좌우로 5의 구역이 3개 이상 있다면 재귀 함수로 돌면서 색칠하도록 했습니다.

이렇게 하니까 경계선 안쪽도 5로 색칠이 됐습니다. FindBoundary 함수로 찾고 -> DFS 재귀로 반복 색칠

 

정리하면 다음과 같습니다.

1. x, y, d1, d2를 정해줍니다. Selection 함수

2. 정해준 기준으로  1 ~ 5 구역을 만들어줍니다. Section 함수

3. 구역을 다 만들었다면 계산해줍니다. Calculate 함수

 

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>

#define MAX 20 + 1
using namespace std;

int N, answer = 987654321;
int stage[MAX][MAX];
int visit[MAX][MAX];

int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };

void ColoringFive(int x1, int y1, int x2, int y2, bool chk1, bool chk2)
{
	if (chk1 && chk2) // x, y 둘다 1씩 증가
	{
		for (int i = x1; i <= x2; i++, y1++)
		{
			visit[i][y1] = 5;
		}
	}
	else if (chk1) // x만 1씩 증가
	{
		for (int i = x1; i <= x2; i++, y1--)
		{
			visit[i][y1] = 5;
		}
	}
}

// 5의 경계선 안쪽에 5로 다 색칠해준다.
void DFS(int x, int y, int color)
{
	visit[x][y] = color;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 1 && ny >= 1 && nx <= N && ny <= N)
		{
			if (visit[nx][ny] == 0)
			{
				DFS(nx, ny, color);
			}
		}
	}
}

// 상하좌우로 5가 색칠되어 있는 곳이 3개라면 그 구역부터 5로 색칠하고 DFS 탐색한다.
void FindBoundary()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int cnt = 0;
			for (int k = 0; k < 4; k++)
			{
				int nx = i + dx[k];
				int ny = j + dy[k];
				if (nx >= 1 && ny >= 1 && nx <= N && ny <= N)
				{
					if (visit[nx][ny] == 5) cnt++;
				}
			}

			if (cnt >= 3)
			{
				DFS(i, j, 5);
			}
		}
	}
}

// 각 구역별로 인구 수를 카운트한다.
void Calculate()
{
	vector<int> total(5, 0);

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			if (visit[i][j] == 1) total[0] += stage[i][j];
			else if (visit[i][j] == 2) total[1] += stage[i][j];
			else if (visit[i][j] == 3) total[2] += stage[i][j];
			else if (visit[i][j] == 4) total[3] += stage[i][j];
			else if (visit[i][j] == 5) total[4] += stage[i][j];
		}
	}
	int max_value = *max_element(total.begin(), total.end());
	int min_value = *min_element(total.begin(), total.end());
	answer = min(answer, max_value - min_value);
}

void Section(int x, int y, int d1, int d2)
{
	// 5 구역 색칠
	visit[x][y] = 5;
	ColoringFive(x + 1, y - 1, x + d1, y - d1, true, false);
	ColoringFive(x + 1, y + 1, x + d2, y + d2, true, true);
	ColoringFive(x + d1, y - d1, x + d1 + d2, y - d1 + d2, true, true);
	ColoringFive(x + d2, y + d2, x + d2 + d1, y + d2 - d1, true, false);
	FindBoundary();
	// 1 구역 색칠
	for (int r = 1; r < x + d1; r++)
	{
		for (int c = 1; c <= y; c++)
		{
			if (visit[r][c] == 0) visit[r][c] = 1;
		}
	}
	// 2 구역 색칠
	for (int r = 1; r <= x + d2; r++)
	{
		for (int c = y + 1; c <= N; c++)
		{
			if (visit[r][c] == 0) visit[r][c] = 2;
		}
	}
	// 3 구역 색칠
	for (int r = x + d1; r <= N; r++)
	{
		for (int c = 1; c < y - d1 + d2; c++)
		{
			if (visit[r][c] == 0) visit[r][c] = 3;
		}
	}
	// 4 구역 색칠
	for (int r = x + d2 + 1; r <= N; r++)
	{
		for (int c = y - d1 + d2; c <= N; c++)
		{
			if (visit[r][c] == 0) visit[r][c] = 4;
		}
	}
}

void Initialize()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			visit[i][j] = 0;
		}
	}
}

void Selection()
{
	for (int x = 1; x <= N; x++)
	{
		for (int y = 1; y <= N; y++)
		{
			for (int d1 = 0; d1 <= N; d1++)
			{
				for (int d2 = 0; d2 <= N; d2++)
				{
					if (x < x + d1 + d2 && x + d1 + d2 <= N)
					{
						if (y - d1 >= 1 && y - d1 < y && y < y + d2 && y + d2 <= N)
						{
							Initialize();           // 방문 초기화
							Section(x, y, d1, d2);  // x, y, d1, d2를 정했다면 구역을 1, 2, 3, 4, 5로 나눠보자.
							Calculate();            // 계산한다.
						}
					}
				}
			}
		}
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> stage[i][j];
		}
	}
	Selection();
	cout << answer;
	return 0;
}