[백준 17779] 게리맨더링 2

++22.11.10 갱신.. 그냥 4중 포문 돌리면 된다. 

이 문제는 AC 받는게 중요한게 아니라, "다이아몬드 형태로 경로 만들어야 할 때 그 경계선을 어떻게 지정해야 하는지"를 알아가면 좋을 듯 싶다. 

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
int N;
int A[20 + 2][20 + 2];
int total;
int bound[20 + 2][20 + 2];

int ans = 0x7fffffff;

void input()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &A[i][j]);
			total += A[i][j];
		}
	}
}


bool make_bound(int x, int y, int d1, int d2)
{
	memset(bound, 0, sizeof(bound));

	// 1구역
	for (int i = 0; i <= d1; i++) {
		int nx = x + i;
		int ny = y - i;
		if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) return false;
		bound[nx][ny] = 5;
	}

	// 2구역
	for (int j = 0; j <= d2; j++) {
		int nx = x + j;
		int ny = y + j;
		if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) return false;
		bound[nx][ny] = 5;
	}

	// 3구역
	for (int j = 0; j <= d2; j++) {
		int nx = x + d1 + j;
		int ny = y - d1 + j;
		if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) return false;
		bound[nx][ny] = 5;
	}

	// 4구역 
	for (int i = 0; i <= d1; i++) {
		int nx = x + d2 + i;
		int ny = y + d2 - i;
		if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) return false;
		bound[nx][ny] = 5;
	}
	return true;
}



int get_area(int x, int y, int d1, int d2)
{
	std::vector<int> V;
	
	int area1 = 0;
	int area2 = 0;
	int area3 = 0;
	int area4 = 0;
	int area5 = 0;

	// 1번 구역
	for (int r = 1; r < x + d1; r++) {
		for (int c = 1; c <= y; c++) {
			if (bound[r][c] == 5) break;
			area1 += A[r][c];
			bound[r][c] = 1;
		}
	}
	V.push_back(area1);

	// 2번 구역
	for (int r = 1; r <= x + d2; r++) { 
		for (int c = N; c > y; c--) {
			if (bound[r][c] == 5) break;
			area2 += A[r][c];
			bound[r][c] = 2;
		}
	}
	V.push_back(area2);

	// 3번 구역
	for (int r = x + d1; r <= N; r++) {
		for (int c = 1; c < y - d1 + d2; c++) {
			if (bound[r][c] == 5) break;
			area3 += A[r][c];
			bound[r][c] = 3;
		}
	}
	V.push_back(area3);

	// 4번 구역
	for (int r = x + d2 + 1; r <= N; r++) { 
		for (int c = N; c >= y - d1 + d2; c--) {
			if (bound[r][c] == 5) break;
			area4 += A[r][c];
			bound[r][c] = 4;
		}
	}
	V.push_back(area4);
	
	// 5번 구역 
	area5 = total - (area1 + area2 + area3 + area4);
	V.push_back(area5);

	std::sort(V.begin(), V.end());	// 벡터는 기본적으로 오름차순 정렬이다. 
	int min = V[0];
	int max = V[4];

	return max - min;
}




void Cal()
{
	for (int x = 1; x <= N; x++) {
		for (int y = 1; y <= N; y++) {	// 기준만들기 
			for (int d1 = 1; d1 < N ; d1++) {
				for (int d2 = 1; d2 < N ; d2++) {
					if (d1 + d2 > N - x || d1 > y - 1 || d2 > N - y) continue;
					if (!make_bound(x, y, d1, d2)) continue;
					int res = get_area(x, y, d1, d2);
					if (ans > res) ans = res;
				}
			}
		}
	}
}



int main()
{
	input();
	Cal();
	printf("%d\n", ans);
	return 0;
}

 

---

지난날의 코드...

#include <cstdio>
#include <algorithm>
int A[20 + 2][20 + 2];
int board[20 + 2][20 + 2];
int visited[20 + 2][20 + 2];
int N;


void input()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &A[i][j]);
		}
	}
}


int get_population(int x, int y, int fd, int td)
{
	// 4. 각 선거구의 인구 구하기  
	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
	int max = 0;
	int min = 0x7fffffff;
	int cnt = 0;

	// 1번 선거구 
	for (int i = 1; i < x + fd; i++) {
		for (int j = 1; j <= y; j++) {
			if (board[i][j] == -1) break;
			visited[i][j] = 1;
			cnt += A[i][j];
		}
	}
	max = (max < cnt) ? cnt : max;
	min = (min > cnt) ? cnt : min;
	cnt = 0;

	// 2번 선거구 
	for (int i = 1; i <= x + td; i++) {
		for (int j = N; j > y; j--) {
			if (board[i][j] == -1) break;
			visited[i][j] = 2;
			cnt += A[i][j];
		}
	}
	max = (max < cnt) ? cnt : max;
	min = (min > cnt) ? cnt : min;
	cnt = 0;

	// 3번 선거구 
	for (int i = x + fd; i <= N; i++) {
		for (int j = 1; j < y - fd + td; j++) {
			if (board[i][j] == -1) break;
			visited[i][j] = 3;
			cnt += A[i][j];
		}
	}
	max = (max < cnt) ? cnt : max;
	min = (min > cnt) ? cnt : min;
	cnt = 0;

	// 4번 선거구 
	for (int i = x + td + 1; i <= N; i++) {
		for (int j = N; j >= y - fd + td; j--) {
			if (board[i][j] == -1) break;
			visited[i][j] = 4;
			cnt += A[i][j];
		}
	}
	max = (max < cnt) ? cnt : max;
	min = (min > cnt) ? cnt : min;
	cnt = 0;
	//debug_v();

	// 5번 선거구 
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (visited[i][j]) continue;
			cnt += A[i][j];
		}
	}
	max = (max < cnt) ? cnt : max;
	min = (min > cnt) ? cnt : min;
	cnt = 0;
	
	//printf("%d %d %d\n", max, min, max - min);
	return max - min;
}




void make_bound(int x, int y, int fd, int td)
{
	// 3. 경계선 구하기 
	for (int i = 0; i <= fd; i++) {
		board[x + i][y - i] = -1;
		board[x + td + i][y + td - i] = -1;
	}
	for (int i = 0; i <= td; i++) {
		board[x + i][y + i] = -1;
		board[x + fd + i][y - fd + i] = -1;
	}
}



int get_bound(int x, int y)
{
	int comp = 0x7fffffff;

	// 2. 기준점(x, y) 에서 경계선의 길이 fd, td 정하기
	for (int fd = 1; fd <= y - 1; fd++) {
		for (int td = 1; td <= N - y; td++) {
			if (fd + td < 2 || fd + td > N - x) continue;
			std::fill(&board[0][0], &board[0][0] + sizeof(board) / sizeof(int), 0);
			make_bound(x, y, fd, td);
			//debug();
			int p = get_population(x, y, fd, td);
			comp = (p < comp) ? p : comp;
		}
	}
	return comp;
}



int simul()
{
	int ans = 0x7fffffff;

	// 1. 기준점 정하기 
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			int sub = get_bound(i, j);	
			ans = (ans > sub) ? sub : ans;
		}
	}
	return ans;
}


int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}