[C/C++] 백준 - 17779번 : 게리맨더링2 (삼성 기출)

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

17779번: 게리맨더링 2

문제

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

선거구를 나누는 방법은 다음과 같다.

1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
2. 다음 칸은 경계선이다.
   1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
   2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
   3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
   4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
   • 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
   • 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
   • 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
   • 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

아래는 크기가 7×7인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

x = 2, y = 4, d1 = 2, d2 = 2	x = 2, y = 5, d1 = 3, d2 = 2	x = 4, y = 3, d1 = 1, d2 = 1

구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

입력

첫째 줄에 재현시의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 A[r][c]를 의미한다.

출력

첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.

 

이 문제는 다른 분들 코드보면 훨 간단하고 쉽게 해결한 것 같다

나는 먼저 d1, d2가 가능한 쌍을 모두 구해야겠다고 생각했고, 거기에서 가능한 x와 y를 구하는 방법으로 했다.

그래서 가능한 모든 쌍을 확인하는 방법을 사용했고, 이 부분은 재귀 및 백트래킹 기법으로 구현하였다.

 

가장 먼저 d1, d2의 범위가

d1, d2 >=1 && 1 <= x < x + d1 + d2 <= N

이므로 첫번째 조건에서 d1, d2가 모두 1보다 크다. 그렇기 때문에 d1 + d2의 가장 작은 수가 2가 된다.

그럼 d1, d2가 될 수 있는 모든 수들은 1부터 N-2가 될 수 있다. 이 수들을 벡터에 넣어준다. 그럼 순열기법을 통해

1부터 N-2의 수 중 2개를 뽑아 만들 수 있는 모든 쌍을 만들 수 있다.

 

그리고 두번째 조건에서 (x + d1 + d2)가 N보다 작거나 같아야한다. 이 말은 (d1 + d2)가 N-1보다 작거나 같아야 한다고 볼 수 있다. 그래서 이 조건을 통해 첫번째 조건으로 만든 2개의 쌍의 값이 두번째 조건에도 만족하는 값인지 확인 할 수 있다.

만약 모든 조건에 만족하는 한 쌍의 값이라면 그 d1, d2로 만들 수 있는 x와 y를 모두 또 다시 만들어주면 된다.

 

x의 모든 값들을 구하는 방법은 x의 조건이

1 ≤ x < x+d1+d2 ≤ N

이므로 1부터 ~  N에서 (d1 + d2)를 뺀 값이 가능한 모든 x의 값이 되며

 

 

 

y의 모든 값들을 구하는 방법은

1 ≤ y-d1 < y < y+d2 ≤ N

이므로 1부터 N까지 모든 수에 대해서 (i라 칭함)

1 <= (i - d1) && (i + d2) <= N

에 만족하는 모든 수들이  y가 될 수 있다.

 

그럼 x와 y의 모든 쌍들도 구했고 그 때의 d1과 d2도 알기 때문에 문제에서 제시한 각 지역구의 범위를 구하고 

가장 인구수가 큰 값과 작은 값의 차이를 구해주면서 최소값을 최신화 해주면 된다.

 

< 코드 >

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#define INF 9876543210
#define ENDL cout << endl;
#define endl '\n'
#define swap(type, x, y) do{type t=y;y=x;x=t;}while(0)
using namespace std;

typedef long long ll;
typedef pair<int, int> pl;

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

struct node {
	bool is;
	int N;
};

int Answer = INF;
node adj[22][22], adj2[22][22];
int N;
vector<int> s;

bool isValid(int y, int x) {
	return (1 <= y && y <= N && 1 <= x && x <= N);
}

void Copy() {
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			adj2[i][j] = adj[i][j];
}

void go(vector<int> &a, vector<int> &b, int depth_a, int depth_b) {
	if (depth_a == a.size()) return;
	if (depth_b == b.size()) {
		go(a, b, depth_a + 1, 0);
		return;
	}

	int x = a[depth_a];
	int y = b[depth_b];
	int d1 = s[0], d2 = s[1];
	Copy();
	int maxV = -1, minV = INF;
	int Area1 = 0, Area2 = 0, Area3 = 0, Area4 = 0, Area5=0;

	int Last = 0;
	for (int i = 0; i <= d1; i++) {
		int pl = x + i, pr = y - i;
		if (isValid(pl, pr) && !adj2[pl][pr].is) {
			adj2[pl][pr].is = true;
			Area5 += adj2[pl][pr].N;
		}
	}
	for (int i = 0; i <= d2; i++) {
		int pl = x + i, pr = y + i;
		if (isValid(pl, pr) && !adj2[pl][pr].is) {
			adj2[pl][pr].is = true;
			Area5 += adj2[pl][pr].N;
		}
	}
	for (int i = 0; i <= d2; i++) {
		int pl = x + d1 + i, pr = y - d1 + i;
		if (isValid(pl, pr) && !adj2[pl][pr].is) {
			adj2[pl][pr].is = true;
			Area5 += adj2[pl][pr].N;
		}
	}
	for (int i = 0; i <= d1; i++) {
		int pl = x + d2 + i, pr = y + d2 - i;
		if (i == d1) Last = pl;
		if (isValid(pl, pr) && !adj2[pl][pr].is) {
			adj2[pl][pr].is = true;
			Area5 += adj2[pl][pr].N;
		}
	}
	for (int row = x + 1; row < Last; row++) {
		bool flag = false;
		for (int l = 1; l <= N; l++) {
			if (flag) {
				if (adj2[row][l].is) break;
				else {
					Area5 += adj2[row][l].N;
					adj2[row][l].is = true;
				}
			}
			if (!adj2[row][l].is) continue;
			flag = true;
		}
	}

	for (int row = 1; row < x + d1; row++) {
		for (int col = 1; col <= y; col++) {
			if (!adj2[row][col].is) Area1 += adj2[row][col].N;
		}
	}

	for (int row = 1; row <= x + d2; row++) {
		for (int col = y+1; col <= N; col++) {
			if (!adj2[row][col].is) Area2 += adj2[row][col].N;
		}
	}

	for (int row = x + d1; row <= N; row++) {
		for (int col = 1; col < y - d1 + d2; col++) {
			if (!adj2[row][col].is) Area3 += adj2[row][col].N;
		}
	}

	for (int row = x + d2 + 1; row <= N; row++) {
		for (int col = y - d1 + d2; col <= N; col++) {
			if (!adj2[row][col].is) Area4 += adj2[row][col].N;
		}
	}
	maxV = max({ Area1, Area2, Area3, Area4, Area5 });
	minV = min({ Area1, Area2, Area3, Area4, Area5 });
	Answer = min(Answer, maxV - minV);

	go(a, b, depth_a, depth_b + 1);
}

void func(vector<int> &v, int depth) {
	if (depth == 2) {
		if (s[0] + s[1] <= N - 1) {
			int Sum = s[0] + s[1];

			vector<int> pos_x, pos_y;
			for (int i = 1; i <= (N - Sum); i++) pos_x.push_back(i);
			for (int i = 1; i <= N; i++) {
				int a = i - s[0];
				int b = i + s[1];
				if (b > N) break;
				if (1 <= a && b <= N) {
					pos_y.push_back(i);
				}
			}
			go(pos_x, pos_y, 0, 0);
		}
		return;
	}

	for (int i = 0; i < v.size(); i++) {
		s.push_back(v[i]);
		func(v, depth + 1);
		s.pop_back();
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int col = 1; col <= N; col++) {
		for (int row = 1; row <= N; row++) {
			cin >> adj[col][row].N;
			adj[col][row].is = false;
		}
	}

	vector<int> v;
	for (int i = 1; i <= N - 2; i++) v.push_back(i);

	func(v, 0);
	cout << Answer << endl;

	return 0;
}