[백준] 17779번: 게리맨더링 2

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

17779번: 게리맨더링 2

나머지 예제 생략

 

문제 이해

식 세우는데 한참 걸렸다.

좌표 이해 안하고 문제에 있는 설명만 복붙해서 풀려다가 한참 걸렸다.

그냥 처음부터 좌표를 볼 걸ㅎㅎ

 

예제 3을 보면 다음과 같이 생겼다.

노란색 칸은 모두 경계선이다. 

내가 최종적으로 푼 방법은, 위와 같은 맵(tmp)을 하나 만드는 것이다.

 

Draw_Map()

• 우선 노란색 경계선을 그린다. (그냥 문제에 있는 식에 맞춰서 그린다)
• 그런 후에, 1선거구, 2선거구, 3선거구, 4선거구를 표시해주면 된다.
  
  • 이 네 선거구는 저 경계선 사각형의 꼭짓점 좌표를 기준으로 칠할 수 있다. 
  • 우선 네 개의 꼭짓점에 0, 1, 2, 3의 넘버를 주고, vertex라는 좌표 배열에 저장한다.
  • 1선거구는 행의 경우 1에서 vertex1의 r-1 까지 , 열의 경우 1에서 vertex0의 c까지이다.
  • 2선거구는 행의 경우 1에서 vertex3의 r까지, 열은 vertex0의c+1부터 N까지이다. 이때 경계선을 침범하지 않을 수 있도록, 노란 칸이 나오면 break해주고 싶기 때문에 1선거구와 다르게, 열을 탐색할 때 N부터 한다.
  • 3선거구와 4선거구도 1, 2선거구처럼 정해주고서 탐색하며 tmp 맵을 채워준다. 
• 이때, 1~4선거구를 칠하면서, 각 선거구 별 인구수를 cnt라는 배열에 계산해준다.
• 위와 같이 tmp를 완성하고 나면 이제 최대 선거구와 최소 선거구의 인구수의 차를 구하는 일만 남았다. 

Get_Min_Diff()

• 5번 선거구의 인구수는 전체 인구수 - (1번 선거구 인구 + 2번 선거구 인구 + 3번 선거구 인구 + 4번 선거구 인구)이다
• 그럼 이제 for 루프를 돌며 최대 선거구와 최소 선거구의 인구수를 구하고, 그 차이를 리턴해주면 된다.
• 이때 만약 인구가 0인 선거구 (한 칸도 없는 경우) 가 있다면 바로 -1을 리턴해서 이 구획은 불가능하다고 알린다.

 

작성 코드

// d1 >= 1 && d2 >= 1
// 1 <= x < x + d1 + d2 <= N
// 1 <= y - d1 < y < y + d2 <= N
// 위의 조건을 만족하는 x, y, d1, d2를 정하고, 선거구 인구 차 구하면 됨
// x가 행, y가 열!
#include <stdio.h>
#include <string.h>
#define MAP_SIZE 20
int N;
int x, y, d1, d2;
int map[MAP_SIZE + 5][MAP_SIZE + 5];
int tmp[MAP_SIZE + 5][MAP_SIZE + 5];
int min_diff = 0x7fffffff;
int sum = 0;
int cnt[5 + 2];

void Get_Input(void) {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
			sum += map[i][j];
		}
	}
}
typedef struct POS {
	int r, c;
}POS;

void Draw_Map(int x, int y, int d1, int d2) {
	memset(cnt, 0, sizeof(cnt));
	memset(tmp, 0, sizeof(tmp));
	POS vertex[4] = { {x, y}, {x + d1, y - d1}, {x + d1 + d2, y - d1 + d2}, {x + d2, y + d2} };
	// 1. 경계선 먼저 표시
	//(x, y), (x+1, y-1), ..., (x+d1, y-d1)
	for (int i = 0; i <= d1; i++) {
		tmp[x + i][y - i] = 5;
	}
	//(x, y), (x+1, y+1), ..., (x+d2, y+d2)
	for (int i = 0; i <= d2; i++) {
		tmp[x + i][y + i] = 5;
	}
	//(x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
	for (int i = 0; i <= d2; i++) {
		tmp[x + d1 + i][y - d1 + i] = 5;
	}
	//(x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
	for (int i = 0; i <= d1; i++) {
		tmp[x + d2 + i][y + d2 - i] = 5;
	}
	
	// 1번
	for (int r = 1; r < vertex[1].r; r++) {
		for (int c = 1; c <= vertex[0].c; c++) {
			if (tmp[r][c] == 5) break;
			tmp[r][c] = 1;
			cnt[1] += map[r][c];
		}
	}
	// 2번
	for (int r = 1; r <= vertex[3].r; r++) {
		for (int c = N; c > vertex[0].c; c--) {
			if (tmp[r][c] == 5) break;
			tmp[r][c] = 2;
			cnt[2] += map[r][c];
		}
	}
	// 3번
	for (int r = vertex[1].r; r <= N; r++) {
		for (int c = 1; c <vertex[2].c; c++) {
			if (tmp[r][c] == 5) break;
			tmp[r][c] = 3;
			cnt[3] += map[r][c];
		}
	}
	// 4번
	for (int r = vertex[3].r+1; r <= N; r++) {
		for (int c = N; c >= vertex[2].c; c--) {
			if (tmp[r][c] == 5) break;
			tmp[r][c] = 4;
			cnt[4] += map[r][c];
		}
	}
}

int Get_Min_Diff(void) {
	cnt[5] = sum - (cnt[1] + cnt[2] + cnt[3] + cnt[4]);
	int max = 0, min = 0x7fffffff;
	for (int i = 1; i <= 5; i++) {
		if (cnt[i] == 0) return -1;
		if (cnt[i] > max) max = cnt[i];
		if (cnt[i] < min) min = cnt[i];
	}
	return max - min;
}

void Solve(void) {
// d1 >= 1 && d2 >= 1
// 1 <= x < x + d1 + d2 <= N  ----> x <= N-d1-d2 == N-2
// 1 <= y - d1 < y < y + d2 <= N ---> 1+1 <= y <= N-1
// 위의 조건을 만족하는 x, y, d1, d2를 정하고, 선거구 인구 차 구하면 됨
	for (int x = 1; x <= N-2; x++) { // x
		for (int y = 2; y <= N-1; y++) { // y
			for (int d1 = 1; d1 < N; d1++) { // d1
				for (int d2 = 1; d2 < N; d2++) { // d2
					// d1과 d2가 불가능한 경우를 가지치기 한다.
					if (x >= x + d1 + d2 || x + d1 + d2 > N) continue;
					if (1 > y - d1 || y - d1 >= y || y >= y + d2 || y + d2 > N) continue;
					// 다 정함 ---> 이제 선거구 별 인구수 구해서 차이 구하면 됨
					Draw_Map(x, y, d1, d2);
					int res = Get_Min_Diff();
					if (res == -1) continue;
					else {
						if (res < min_diff) min_diff = res;
					}
				}
			}
		}
	}
}

int main(void) {
	Get_Input();
	Solve();
	printf("%d", min_diff);
	return 0;
}