[BOJ 17779] 게리맨더링2 (c++)

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

문제 개요

N×N 크기의 격자로 이루어진 재현시를 5개의 선거구로 나누는 문제입니다. 기준점 (x, y)와 경계 길이 d1, d2를 정해 특정 규칙에 따라 선거구를 구획하고, 각 선거구의 인구수 차이를 최소화해야 합니다.

• 기준점과 경계 길이로 4개의 경계선을 그어 5번 선거구(중앙)를 만든다
• 나머지 구역은 경계선을 기준으로 1, 2, 3, 4번 선거구로 분류된다
• 구가 가장 많은 선거구와 가장 적은 선거구의 차이를 최소화해야 한다.

(d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)

(5 ≤ N ≤ 20)

(1 ≤ A[r][c] ≤ 100)

문제 풀이

인구가 가장 많은 선거구와 가장 적은 선거구의 차이를 최소화해야 한다이 문제는 완전 탐색 문제입니다. 가능한 모든(x, y, d1, d2) 조합을 시도하여, 각 경우에 대해 인구 차이를 계산해야 합니다. 먼저 4중 for문을 통해 가능한 모든 조합을 시도하고, find_area()함수를 통해 좌표가 어느 선거구의 속하는지를 판단하여 인구를 더해 계산하였습니다. find_area()의 분류 로직은 다음과 같이 작성하였습니다.
  1. i가 x보다 작은 경우엔 j <= y인 경우는 모두 1번 구역, j > y인 경우는 모두 2번 구역
  2. i가 x + d1 + d2보다 큰 경우엔 j < y - d1 + d2인 경우는 모두 4번 구역, j >= y - d1 + d2인 경우는 모두 3번 구역
  3. x <= i < x + d1 이고, j < y - (i - x)인 경우는 모두 1번 구역
  4. x <= i <= x + d2 이고, j > y + (i - x)인 경우는 모두 2번 구역
  5. x + d1 <= i <= x + d1 +d2 이고, j < y - d1 + d2 - ( x + d1 + d2 - i)의 경우는 모두 3번 구역
  6. x + d2 < i <= x + d1 + d2 이고, j > y - d1 + d2 + ( x + d1 + d2 - i)의 경우는 모두 4번구역
  7. 이외에는 모두 5번 구역

코드

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

int n, res = 1e9;
int graph[21][21];
int people[5];

int find_area(int i, int j, int x, int y, int d1, int d2) {
	if (i < x) {
		if (j <= y) {
			return 0;
		}
		else {
			return 1;
		}
	}
	else if (x <= i && i < x + d1 && j < y - (i - x)) {
		return 0;
	}
	else if (x <= i && i <= x + d2 && j > y + (i - x)) {
		return 1;
	}
	else if (x + d1 <= i && i <= x + d1 + d2 && j < (y - d1 + d2) - (x + d1 + d2 - i)) {
		return 2;
	}
	else if (x + d2 < i && i <= x + d1 + d2 && j > (y - d1 + d2) + (x + d1 + d2 - i)) {
		return 3;
	}
	else if (i > x + d1 + d2) {
		if (j < (y - d1 + d2)) {
			return 2;
		}
		else {
			return 3;
		}
	}
	else {
		return 4;
	}
}

int func(int x, int y, int d1, int d2) {
	memset(people, 0, sizeof(people));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int area = find_area(i, j, x, y, d1, d2);
			people[area] += graph[i][j];
		}
	}
	int mn = 1e9;
	int mx = 0;
	for (int i = 0; i < 5; i++) {
		mx = max(mx, people[i]);
		mn = min(mn, people[i]);
	}
	return mx - mn;

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> graph[i][j];
		}
	}
	for (int x = 1; x < n - 1; x++) {
		for (int y = 2; y < n; y++) {
			for (int d1 = 1; y - d1 > 0; d1++) {
				for (int d2 = 1; y + d2 <= n && x + d1 + d2 <= n; d2++) {
					res = min(func(x, y, d1, d2), res);
				}
			}
		}
	}
	cout << res;
	return 0;
}