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

문제 링크

---

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

17779번: 게리맨더링 2

 

접근 방법

---

이 문제는 구역만 조건에 따라 잘 나눠 주면 된다. 구역에 대한 합을 구하며 방문여부를 체크하자.

 

구역 1: 빨간색

구역 2: 노란색

구역 3: 파란색

구역 4: 초록색

구역 5: 갈색 테두리를 포함한 흰색

n = 8, x = 2, y = 4, d1 = 2,  d2 = 2 일때의 예시

(1) 구역 1

 구역 1에 대한 범위는 문제에 주어졌듯이 1 ≤ i < x+d1, 1 ≤ j ≤ y 이다. 하지만 이 범위에서 그림에서 빨간 부분만 표현하기 위해서는 갈색부분을 포함한 흰색 부분을 제외해야 한다. 이를 포함하지 않을 조건으로는 빨간색과 인접한 갈색부분을 보자. 그 갈색 부분의 합은 x+y=6으로 일정하다. 그러므로 모든 빨간부분은

i+j <x+y= 6이다.  

int area1(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = 1; i < x + d1; i++)
		for (int j = 1; j <= y; j++) {
			if (i + j < x + y) {
				visited[i][j] = 1;
				sum += map[i][j];
			}
		}
	return sum;
}

(2) 구역 2

 구역 2에 대한 범위는 1 ≤ i ≤ x+d2, y < j ≤ N 이다. 하지만 이 범위에서 그림에서 노란 부분만 표현하기 위해서는 갈색부분을 포함한 흰색 부분을 제외해야 한다. 이를 포함하지 않을 조건으로는 빨간색과 인접한 갈색부분을 보자. 그 갈색 부분의 차는 y - x = 2로 일정하다. 그러므로 모든 노란부분은 (y - x = 2) < j - i

이다.

int area2(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = 1; i <= x + d2; i++) 
		for (int j = y+1; j <= n; j++) {
			if (y - x < j - i) {
				visited[i][j] = 2;
				sum += map[i][j];
			}
		}
	return sum;
}

(3) 구역 3

 구역 3에 대한 범위는 x+d1 ≤ i ≤ N, 1 ≤ j < y-d1+d2이다. 하지만 이 범위에서 그림에서 파란 부분만 표현하기 위해서는 갈색부분을 포함한 흰색 부분을 제외해야 한다. 이를 포함하지 않을 조건으로는 파란색과 인접한 갈색부분을 보자. 그 갈색 부분의 차는 x - y + 2 * d1 = 2로 일정하다.

그러므로 모든 파란부분은 (y - x + 2 * d1 = 2) < i - j 이다.

int area3(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = x + d1; i <= n; i++) 
		for (int j = 1; j < y - d1 + d2; j++) 
			if (x - y + 2 * d1 < i - j) {
				visited[i][j] = 3;
				sum += map[i][j];
			}
	return sum;
}

(4) 구역 4

 구역 4에 대한 범위는 x+d2 < i ≤ N, y-d1+d2 ≤ j ≤ N이다. 하지만 이 범위에서 그림에서 초록 부분만 표현하기 위해서는 갈색부분을 포함한 흰색 부분을 제외해야 한다. 이를 포함하지 않을 조건으로는 초록색과 인접한 갈색부분을 보자. 그 갈색 부분의 합은 x + y + 2 * d2 = 10으로 일정하다.

그러므로 모든 파란부분은 (x + y + 2 * d2 = 10) < i + j 이다.

int area4(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = x + d2 + 1; i <= n; i++) 
		for (int j = y - d1 + d2; j <= n; j++) 
			if (i + j > x + y + 2 * d2) {
				visited[i][j] = 4;
				sum += map[i][j];
			}
	return sum;
}

(5) 구역 5

 구역 1,2,3,4를 제외한 모든 부분이다.

 

소스 코드

---

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

int map[21][21];
int visited[21][21];
int n;

int area1(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = 1; i < x + d1; i++)
		for (int j = 1; j <= y; j++) {
			if (i + j < x + y) {
				visited[i][j] = 1;
				sum += map[i][j];
			}
		}
	return sum;
}
int area2(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = 1; i <= x + d2; i++) 
		for (int j = y+1; j <= n; j++) {
			if (y - x < j - i) {
				visited[i][j] = 2;
				sum += map[i][j];
			}
		}
	return sum;
}
int area3(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = x + d1; i <= n; i++) {
		for (int j = 1; j < y - d1 + d2; j++) {
			if (x - y + 2 * d1 < i - j) {
				visited[i][j] = 3;
				sum += map[i][j];
			}
		}
	}
	return sum;
}
int area4(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = x + d2 + 1; i <= n; i++) {
		for (int j = y - d1 + d2; j <= n; j++) {
			if (i + j > x + y + 2 * d2) {
				visited[i][j] = 4;
				sum += map[i][j];
			}
		}
	}
	return sum;
}
int area5(int x, int y, int d1, int d2) {
	int sum = 0;
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= n; j++) 
			if (visited[i][j] == 0) {
				visited[i][j] = 5;
				sum += map[i][j];
			}
	return sum;
}

int make_area(int x, int y, int d1, int d2) {

	int cnt1 = area1(x, y, d1, d2);
	int cnt2 = area2(x, y, d1, d2);
	int cnt3 = area3(x, y, d1, d2);
	int cnt4 = area4(x, y, d1, d2);
	int cnt5 = area5(x, y, d1, d2);

	int maxi = max(cnt1, max(cnt2, max(cnt3, max(cnt4, cnt5))));
	int mini = min(cnt1, min(cnt2, min(cnt3, min(cnt4, cnt5))));
	return maxi - mini;
}

int solve(){
	int result = 0xFFFFFFF;
	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 (1 <= x && x + d1 + d2 <= n && 1 <= y - d1 && y + d2 <= n) {
						memset(visited, 0, sizeof(visited));
						result = min(result, make_area(x, y, d1, d2));
					}
	return result;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> map[i][j];
	cout << solve() << endl;
}

개발 환경 : VS 2019

질문, 지적 환영입니다.