[백준 17779: 게리맨더링 2] (C++)

삼성 SW 역량테스트 기출 문제

https://www.acmicpc.net/workbook/view/1152

ㄴ게리맨더링 2

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

 

 

 

l 문제

 

1. 재현시의 시장 구재현은 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

2. 재현시 는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다.

3. 선거구, 구역 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다.  중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

4. 선거구를 나누는 방법은 다음과 같다.

기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2≥ 1, 1 ≤ x < x+d1+d2≤ N, 1 ≤ y-d1< y < y+d2≤ N) 다음 칸은 경계선이다. (x, y), (x+1, y-1), ..., (x+d1, y-d1) (x, y), (x+1, y+1), ..., (x+d2, y+d2) (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2) (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1) 경계선과 경계선의 안에 포함되어있는 5번 선거구이다. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다. 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

5. 구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

 

 

 

l 입력

 

첫째 줄에 재현시의 크기 N이 주어진다. ( 5 ≤ N ≤ 20 )

둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 A[r][c]를 의미한다. ( 1 ≤ A[r][c] ≤ 100 )

 

 

l 출력

 

첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.

 

 

l 풀이

 

브루트포스로 모든 경우를 시도 5번 선거구 경계선을 만들고 인구 수를 Count 1~4번 선거구는 조건에 따라 Count 하면 된다. ( 5번 선거구와 겹치지 않도록 처리 )

선거구 선택 함수 {   2. 5번 선거구 경계선   3. 5번 선거구 내부 탐색   4. 1 ~ 4 선거구 선택   5. 가장 작은 최대 인구, 최소 인구의 차이로 갱신 } 브루트 포스 함수 {   1. 가능한 위치( x, y )에서 d1, d2를 늘여가며 시도    for( x = 1 ~ N-2 )       for( y = 2 ~ N-1 ) 까지만 탐색하면 됨           d1 =1, d2 = 1           조건을 만족하는 동안 선거구 선택, ++d2           만족하지 않으면 ++d1, d2 = 1, 이것 또한 조건을 만족할 때까지 진행 }

5 번 선거구

경계선 그리기 1, 4번 조건이 d1으로 같이 묶이고 2, 3번 조건이 d2로 같이 묶여서 각각 for문을 돌렸습니다. 내부 탐색 경계선을 그리면서 동시에 인구 수를 Count하는 방법이 없을까 하고 생각을 많이 했는데 결국 생각이 안나서 경계선의 내부를 탐색하는 방법을 선택했습니다.   아이디어   시작 위치의 바로 아래 칸은 항상 비어있다는 점에서 착안하여   ( x, y ) 위치에서 좌측, 우측 대각선으로 각각 내려가면서   ( x+1, y ) 위치에서 탐색을 시작하는 것입니다.    방법 1) 경계선 내부를 다 채울 때까지 DFS로 탐색    방법 2) 반대 편 경계선을 만날 때까지 x축 증가하면서 탐색    어떤 방법을 쓰던지 자기 마음이고, 인구 수만 제대로 알아내면 됩니다.

1~4 번 선거구

문제에 주어진 조건에 따라 선택하면 됩니다. 혹시 몰라서 1. 모든 구역이 선택되었는가? 2. 구역을 하나도 선택 못한 선거구가 있는가? 3. 각 선거구 마다 선택한 구역이 인접한가? 이런 것들을 모두 검사했었는데 굳이 검사를 안해줘도 통과합니다. 문제 없습니다.

 

 

l  코드

 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int FIVE = 4;

int N, board[21][21], people[5], ans;
bool visited[21][21];
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0 ,-1 ,0 };

void select_five_area(int x, int y, int d1, int d2)
{
	int i, j;
	memset(people, 0, sizeof(people));
	memset(visited, 0, sizeof(visited));

	// 2. 5번 선거구 경계선
	for (i = 0; i <= d1; ++i)
	{
		visited[x + i][y - i] = true;
		visited[x + d2 + i][y + d2 - i] = true;
		people[FIVE] += board[x + i][y - i] + board[x + d2 + i][y + d2 - i];
	}
	for (i = 1; i < d2; ++i)
	{
		visited[x + i][y + i] = true;
		visited[x + d1 + i][y - d1 + i] = true;
		people[FIVE] += board[x + i][y + i] + board[x + d1 + i][y - d1 + i];
	}

	// 3. 5번 선거구 내부 탐색
	for (i = 0; i < d1; ++i)
	{
		j = 0;
		while (!visited[x + i + j + 1][y - i])
		{
			visited[x + i + j + 1][y - i] = true;
			people[FIVE] += board[x + i + j + 1][y - i];
			++j;
		}
	}
	for (i = 1; i < d2; ++i)
	{
		j = 0;
		while (!visited[x + i + j + 1][y + i])
		{
			visited[x + i + j + 1][y + i] = true;
			people[FIVE] += board[x + i + j + 1][y + i];
			++j;
		}
	}
 	// 4. 1 ~ 4 선거구 선택
	for (i = 1; i <= N; ++i)
	{
		for (j = 1; j <= N; ++j)
		{
			if (visited[i][j] == true) continue;
			if (i < x + d1 && j <= y)                people[0] += board[i][j];
			else if (i <= x + d2 && y < j)           people[1] += board[i][j];
			else if (x + d1 <= i && j < y - d1 + d2) people[2] += board[i][j];
			else if (x + d2 < i && y - d1 + d2 <= j) people[3] += board[i][j];
		}
	}

	// 5. 가장 작은 최대 인구, 최소 인구의 차이로 갱신
	pair<int*, int*> p = minmax_element(people, people + 5);
	ans = min(ans, int(*p.second - *p.first));
}

void divide_area()
{
	int x, y, d1, d2;

	// 1. 가능한 위치에서 d1, d2를 늘여가며 시도
	for (x = 1; x <= N - 2; ++x)
	{
		for (y = 2; y <= N - 1; ++y)
		{
			d1 = 1, d2 = 1;

			while (true)
			{
				if (x + d1 + d2 <= N && 1 <= y - d1 && y + d2 <= N)
					select_five_area(x, y, d1, d2++);
				else
				{
					++d1, d2 = 1;
					if (!(x + d1 + d2 <= N && 1 <= y - d1 && y + d2 <= N))
						break;
				}
			}
		}
	}
}

int main()
{
	// freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	register int i, j;
	for (i = 1; i <= N; ++i)
		for (j = 1; j <= N; ++j)
			cin >> board[i][j];

	ans = 987654321;
	divide_area();
	cout << ans;
	return 0;
}

 

느낀점

 

삼성 SW 역량 테스트는 완전 탐색, 시뮬레이션 이라는 틀 안에서 점점 난이도를 높이기 위해

자잘한 조건을 많이 추가해서 구현하기 까다롭게 만드는 것 같습니다.

문제 읽고 이해하는데에도 시간이 많이 걸렸습니다...ㅎㅎ