boj, 백준) 17779. 게리맨더링 2 ( C / C++)

1. 문제 링크

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

17779번: 게리맨더링 2

2. 문제 개요

 선거구를 적절히 나누어 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

 

3. 문제 힌트

   구현력 -> 경계선, 각 선거구의 구역 범위 처리 잘하기.

   Brute Force . N이 최대 20밖에 안됨. 모든 칸을 선거구 5의 기준점이라 가정, 모든 범위(d1, d2의 모든 경우의 수)를 탐색해도 무리가 없음.

 

4. 문제 풀이

 이 문제는 문제에 주어진 조건을 얼마나 코드로 잘 옮기느냐에 따라서 난이도가 결정된다고 생각한다.

경계선의 범위나 각 선거구의 범위는 문제에 잘 주어져 있다.

우선 보기나 예에서 x,y가 선거구 5의 가장 윗점이므로,  x, y 선거구 5의 윗점이라 가정하고 모두 (N*N) 탐색한다.

기준점을 정하고 d1, d2를 (1~최대 N-1)까지 늘려보고 구역을 분리한다.

구역을 정할 때는 BFS를 사용하여 정한다.

그렇게 구역을 분리하고 선거구 별 인구를 합해서 인구 차이가 최소가 되는 값을 찾는다.

-반복-

 

5. 코드

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

int n;
int a[20][20];
int ret = 123456789;

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

int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> a[i][j];

	for (int x = 0; x < n-2; ++x)
	{
		for (int y = 1; y < n - 1; ++y)
		{
			for (int d1 = 1; d1 < y; ++d1)
			{
				for (int d2 = 1; y + d2 < n; ++d2)
				{
					//boundary check;
					if (x + d1 + d2 >= n)	continue;
					if (y - d1 < 0 || y + d2 >= n)	continue;

					//draw a line which have 5 value
					int mask[20][20] = { 0 };
					for (int i = 0; i <= d1; ++i)
					{
						mask[x + i][y - i] = 5;
						mask[x + d2 + i][y + d2 - i] = 5;
					}
					for (int i = 0; i <= d2; ++i)
					{
						mask[x + i][y + i] = 5;
						mask[x + d1 + i][y - d1 + i] = 5;
					}

					//BFS
					queue <pair<int, int>> q;
					bool visited[20][20] = { false };

					q.push(make_pair(0, 0));	//1
					mask[0][0] = 1;
					q.push(make_pair(0, n - 1));	//2
					mask[0][n - 1] = 2;
					q.push(make_pair(n - 1, 0));	//3
					mask[n - 1][0] = 3;
					q.push(make_pair(n - 1, n - 1));//4
					mask[n - 1][n - 1] = 4;
					visited[0][0] = true;
					visited[0][n - 1] = true;
					visited[n - 1][0] = true;
					visited[n - 1][n - 1] = true;

					while (!q.empty())
					{
						int cx = q.front().first;
						int cy = q.front().second;
						q.pop();

						for (int dir = 0; dir < 4; ++dir)
						{
							int nx = cx + dx[dir];
							int ny = cy + dy[dir];

							if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny] || mask[nx][ny] == 5)
								continue;

							//masking
							if ((0 <= nx && nx < x + d1) && (0 <= ny && ny <= y))
								mask[nx][ny] = 1;

							if ((0 <= nx && nx <= x + d2) && (y < ny && ny < n))
								mask[nx][ny] = 2;

							if ((x + d1 <= nx && nx < n) && (0 <= ny && ny < y - d1 + d2))
								mask[nx][ny] = 3;

							if ((x + d2 < nx && nx < n) && (y - d1 + d2 <= ny && ny < n))
								mask[nx][ny] = 4;

							visited[nx][ny] = true;
							q.push(make_pair(nx, ny));
						}
					}

					for (int i = 0; i < n; ++i)
						for (int j = 0; j < n; ++j)
							if (mask[i][j] == 0)
								mask[i][j] = 5;

					//separation finished.
					int minval = 123456789;
					int maxval = -123456789;

					int val[5] = { 0 };
					for (int i = 0; i < n; ++i)
					{
						for (int j = 0; j < n; ++j)
						{
							if (mask[i][j] == 1)
							{
								val[0] += a[i][j];
							}
							else if (mask[i][j] == 2)
							{
								val[1] += a[i][j];
							}
							else if (mask[i][j] == 3)
							{
								val[2] += a[i][j];
							}
							else if (mask[i][j] == 4)
							{
								val[3] += a[i][j];
							}
							else if (mask[i][j] == 5)
							{
								val[4] += a[i][j];
							}
						}
					}
					for (int i = 0; i < 5; ++i)
					{
						minval = min(minval, val[i]);
						maxval = max(maxval, val[i]);
					}
					ret = min(ret, maxval - minval);
				}
			}
		}
	}

	cout << ret;
	return 0;
}

6. 결과 사진

※이 알고리즘으로는 약 80ms가 최대인 것 같다. 채점 현황을 보니 C++14 20ms가 나오던데 다른 분들의 풀이도 참고해봐야겠다.

 

지적, 댓글 언제나 환영입니다~