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

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

17779번: 게리맨더링 2

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

int N;
int A[21][21];
int ans = 987654321;
int graph[21][21];

//x,y,d1,d2 가능한 조건인지 체크
bool isPossible(int x, int y, int d1, int d2) {
	if (x + d1 + d2 > N) {
		return false;
	}
	if (y - d1 >= 1 && y - d1 < y && y < y + d2 && y + d2 <= N) {
		return true;
	}
	return false;
}

struct {
	bool operator() (pair<int, int> a, pair<int, int> b) const {
		if (a.first == b.first)
			return a.second < b.second;
		return  a.first < b.first;
	}
} cmp;

int region_five(int x, int y, int d1, int d2) {
	int sum = 0;
	vector<pair<int, int> > boundary;
	for (int i = 0; i <= d1; i++) {
		int new_row = x + i;
		int new_col = y - i;
		if (graph[new_row][new_col] == 0) {
			graph[new_row][new_col] = 5;
			sum += A[new_row][new_col];
			boundary.push_back({ new_row,new_col });
		}
	}
	for (int i = 0; i <= d2; i++) {
		int new_row = x + i;
		int new_col = y + i;
		if (graph[new_row][new_col] == 0) {
			graph[new_row][new_col] = 5;
			sum += A[new_row][new_col];
			boundary.push_back({ new_row,new_col });
		}
	}
	for (int i = 0; i <= d2; i++) {
		int new_row = x + d1+i;
		int new_col = y - d1+i;
		if (graph[new_row][new_col] == 0) {
			graph[new_row][new_col] = 5;
			sum += A[new_row][new_col];
			boundary.push_back({ new_row,new_col });
		}
	}
	for (int i = 0; i <= d1; i++) {
		int new_row = x + d2 + i;
		int new_col = y + d2 - i;
		if (graph[new_row][new_col] == 0) {
			graph[new_row][new_col] = 5;
			sum += A[new_row][new_col];
			boundary.push_back({ new_row,new_col });
		}
	}
	sort(boundary.begin(), boundary.end(), cmp);			//경계선 안쪽 값 채워주기
	for (int i = 1; i < boundary.size() - 1; i+=2) {
		int start_row = boundary[i].first; 
		int start_col = boundary[i].second;
		int end_col = boundary[i+1].second;
		for (int j = start_col + 1; j < end_col; j++) {
			graph[start_row][j] = 5;
			sum += A[start_row][j];
		}
	}
	return sum;
}

int region_one(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 (graph[i][j] == 0) {
				graph[i][j] = 1;
				sum += A[i][j];
			}
		}
	}
	return sum;
}

int region_two(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 (graph[i][j] == 0) {
				graph[i][j] = 2;
				sum += A[i][j];
			}
		}
	}
	return sum;
}

int region_three(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 (graph[i][j] == 0) {
				graph[i][j] = 3;
				sum += A[i][j];
			}
		}
	}
	return sum;
}

int region_four(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 (graph[i][j] == 0) {
				graph[i][j] = 4;
				sum += A[i][j];
			}
		}
	}
	return sum;
}

int main() {
	cin >> N;
	int x, y, d1, d2;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> A[i][j];
		}
	}
	//x,y,d1,d2 선정
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			x = i; y = j;
			for (int k = 1; k <= N; k++) {
				for (int l = 1; l <= N; l++) {
					d1 = k; d2 = l;
					if (isPossible(x, y, d1, d2)) {
						vector<int> v;
						memset(graph, 0, sizeof(graph));
						v.push_back(region_five(x, y, d1, d2));
						v.push_back(region_one(x, y, d1, d2));
						v.push_back(region_two(x, y, d1, d2));
						v.push_back(region_three(x, y, d1, d2));
						v.push_back(region_four(x, y, d1, d2));
						sort(v.begin(), v.end());
						ans = min(ans, abs(v.front()-v.back()));
					}
				}
			}
		}
	}
	cout << ans << "\n";
	return 0;
}

구현 문제.

 

문제 조건을 그대로 따라 준 다음 5번 영역의 경계선 안쪽을 표시하는 부분에는, 경계선 좌표들을 오름차순으로 VECTOR에 넣어서 양 끝을 제거한뒤, 남은 좌표들에 한해서 첫번째 좌표~두번째 좌표까지의 영역을 칠해준다.

다른 분들의 코드를 보니 움직이는 방향을 이용해서 경계선 칠할 때 같이 칠하는 방법도 있다.