[BOJ 17779] 게리맨더링2

문제출처

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

17779번: 게리맨더링 2

 

문제풀이

문제를 이해하는데 너무 오래걸렸다. 이해력이 부족한건가..

n X n 배열에서 5개의 선거구를 만들어 선거구의 인구의 최댓값과 최솟값의 차이가 가장 적은 결과를 출력하는 문제이다.

 

이 문제는 가장 중요한게 1, 2, 3, 4번 지구의 경계선을 어떻게 나누는지 이해하는게 가장 중요하다.

처음에 d1과 d2의 값을 어떻게 해야 하는지 고민이 많았는데 문제를 자세히 읽고 1, 2, 3, 4번 꼭지점의 좌표를 적어보면 이해하기 편하다.

 

 

 

1번 : (y, x)

2번 : (y+d2, x+d2)

3번 : (y+d1, x-d1)

4번 : (y+d1+d2, x-d1+d2)

즉, d1은 왼쪽대각선으로 이동하는 칸의 수이고 d2는 오른쪽대각선으로 이동하는 칸의 수임을 유추할 수 있다.

그러면 d1의 범위를 알 수 있다. d1은 3번꼭지점의 x좌표를 기준으로 생각해 보자.

3번 꼭지점의 x-d1은 0이거나 0보다 커야한다. (x-d1 >= 0) 이 식을 d1으로 정리하면 d1<= x의 식이 나온다.

마찬가지로 d2의 범위는 2번 꼭지점의 x좌표를 기준으로 생각해보자. 

x+d2는 마찬가지고 n X n 배열을 벋어날수 없기 때문에 x+d2 <= n의 식이 나오고 정리하면 d2 <= n-x 이다.

 

위와 같이 d1과 d2의 범위를 구하고 전체탐색을 한다. 이때 y, x, d1, d2의 값으로 경계선을 만들 수 없는 경우는 제외한다. 경계선을 만들 수 있으면 꼭지점 정보를 vector에 저장하고 1번 지역구부터 4번 지역구까지 tempMap에 값을 넣어줬다.

 

1번 선거구의 경우 0행부터 3번꼭지점 행-1까지 범위안에 들어와야한다.  열은 0열부터 1번꼭지점까지의 열이다.

이때 그림을 보면 y값(행)이 증가할때 마다 열값이 1개씩 감소하는 것을 알 수 있다. 때문에 y값(행)이 1번꼭지점의 y값보다 크거나 같으면 갯수를 세어 열을 채워줄때 빼줬다. 이후 2, 3, 4번 지역구도 동일하게 진행.

이 부분은 코드를 보는게 더 이해가 빠를듯 하다.

 

이후 n X n 배열을 순회하면서 1~5번의 값을 기준으로 map에 있는 인구수를 벡터에 저장해 오름차순으로 정렬한뒤 차이를 구했다. 이 차이는 경계선이 정상적으로 그려질때의 값이므로 값을 구할때마다 min함수를 이용해 차이를 최신화해줬다.

 

문제를 이해하는게 정말 어려웠다. 처음에 y, x, d1, d2의 부등식을 정리하려고 애썼는데 사실 지금도 어떻게 정리하는지 모르겠다... (혹시 x<x+d1+d2<=n, 1<=y-d1<y<y+d2<=n) 이 식을 정리해서 문제풀이 하신분 댓글 부탁드립니다.

 

삼성기출 문제가 최신문제일수록 좀더 난이도가 생기는 느낌이다. 뭔가 전체탐색을 하면서 시뮬레이션이 섞여있거나 시뮬레이션 조건이 까다로워지는건 나만의 느낌인가....?

 

소스코드

https://github.com/sw93/algorithm/blob/master/SW_TEST(samsung)/BOJ_17779/boj17779.cpp

sw93/algorithm

 

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;
int n, ans = INF;
int map[20][20];
int tempMap[20][20];
vector<pair<int, int> > v;
void init() {
	cin >> n;
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			cin >> map[y][x];
		}
	}
}
bool checkBoard(int y, int x, int d1, int d2) {

	// 3번 꼭지점
	if (y + d1 >= n || x - d1 < 0) return false;

	// 2번 꼭지점
	if (y + d2 >= n || x + d2 >= n) return false;

	// 4번 꼭지점
	if (y + d1 + d2 >= n || x - d1 + d2 < 0) return false;
	return true;
}
void calc() {
	vector<int> ret(5, 0);
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			if (tempMap[y][x] == 1) ret[0] += map[y][x];
			else if (tempMap[y][x] == 2) ret[1] += map[y][x];
			else if (tempMap[y][x] == 3) ret[2] += map[y][x];
			else if (tempMap[y][x] == 4) ret[3] += map[y][x];
			else if (tempMap[y][x] == 5) ret[4] += map[y][x];
		}
	}

	sort(ret.begin(), ret.end());
	int diff = ret[4] - ret[0];
	ans = min(ans, diff);
}
void solve() {

	// 5번 지역구로 모두 초기화 (1, 2, 3, 4번 지역구가 아니면 5번 지역구)
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			tempMap[y][x] = 5;
		}
	}

	// 1번 지역구
	int minusCount = 0;
	for (int y = 0; y < v[1].first; y++) {
		if (y >= v[0].first) minusCount++;
		for (int x = 0; x <= v[0].second - minusCount; x++) {
			tempMap[y][x] = 1;
		}
	}

	// 2번 지역구
	minusCount = 0;
	for (int y = 0; y <= v[2].first; y++) {
		if (y > v[0].first) minusCount++;
		for (int x = v[0].second + minusCount + 1; x < n; x++) {
			tempMap[y][x] = 2;
		}
	}

	// 3번 지역구
	minusCount = 0;
	for (int y = n - 1; y >= v[1].first; y--) {
		if (y < v[3].first) minusCount++;
		for (int x = 0; x < v[3].second - minusCount; x++) {
			tempMap[y][x] = 3;
		}
	}

	// 4번 지역구
	minusCount = 0;
	for (int y = n - 1; y > v[2].first; y--) {
		if (y <= v[3].first) minusCount++;
		for (int x = v[3].second + minusCount; x < n; x++) {
			tempMap[y][x] = 4;
		}
	}

	calc();
	v.clear();
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	init();
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {

			// d1 = 왼쪽 대각선 이동
			// 3번 꼭지점 = (y+d1, x-d1)
			// x-d1값이 0보다 크거나 같아야 함 (x - d1 >= 0)
			// 따라서 d1 <= x
			for (int d1 = 1; d1 <= x; d1++) {

				// d2 = 오른쪽 대각선 이동
				// 2번 꼭지점 = (y+d2, x+d2)
				// x+d2값이 n보다 작거나 같아야 함 (x + d2 <= n)
				// 따라서 d2 <= n-x
				for (int d2 = 1; d2 <= n - x; d2++) {
					if (checkBoard(y, x, d1, d2)) {
						// 선거구 경계 위치
						v.push_back(make_pair(y, x));
						v.push_back(make_pair(y + d1, x - d1));
						v.push_back(make_pair(y + d2, x + d2));
						v.push_back(make_pair(y + d1 + d2, x - d1 + d2));
						solve();
					}
				}
			}
		}
	}
	cout << ans;
	return 0;
}