boj, 백준) 17779 개리맨더링2 ( C++)

1. 문제 링크

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

17779번: 게리맨더링 2

2. 문제 개요

 선거구를 5개로 나누어 5개 중 인구 차이가 최소가 되는 경우(값)를 구하기.

 

3. 문제 힌트

   완전탐색하기. (x, y, d1, d2)가 나올 수 있는 모든 경우의 수 검사.

 

4. 문제 풀기

 이번문제의 코드가 상대적으로 길어서 흐름 위주로 풀이를 쓰겠습니다.

 

우선, 값을 입력받고, 완전탐색으로 x y d1 d2를 정한다.

하나의 테스트 케이스(x y d1 d2)에서 어떻게 동작하는지 살펴보면,

 

값(x, y, d1, d2)을 토대로 이런형태로 구역을 갈라야 한다.

 

(1) 구역을 가르기 위해서는 테두리를 먼저 그려야 한다.

   - 테두리는 문제에 주어진대로 구현한다.

(참고)

1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

 (2) 테두리를 그리고 나면, 이제 구역을 나눌 수 있는데, 어떠한 경우라도 밑의 빨간색으로 체크된 부분은 각각 1, 2, 3, 4 구역에 속하게 된다. 그래서 문제에 주어진 조건에 알맞게 범위를 정한 뒤, 빨간색으로 체크된 부분을 기점으로 BFS탐색을 진행한다. (5를 만나면 멈출 것)

(참고)

• 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
• 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
• 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
• 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

 

(3) 구역 5는 마지막에 BFS로 채우거나 아니면 채워지지 않은 부분을 5로 채우면서 구역을 정할 수 있다.(단순 반복문 or BFS) 코드에서는 단순 반복문으로 구현하였다. 

즉, 완전 탐색으로 x, y, d1, d2를 구하고, 각 경우의 수마다 맵을 전체 탐색하니까 N^4(완전 탐색), N^2(BFS) 따라서 O(N^6)의 시간 복잡도를 갖는 코드이다.

 

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 one more time.
					if (x + d1 + d2 >= n)	continue;
					if (y - d1 < 0 || y + d2 >= n)	continue;

					//draw a line
					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;

					
					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;
}

 

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