백준(BOJ) 17779번 게리맨더링2

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

17779번: 게리맨더링 2

풀이 :

 

1.

- 우선 주어진 y, x와 d1, d2를 모르기 때문에 하나하나 다 해보아야 한다. 4중 for문을 이용해서

 

그냥 주어진 범위를 벗어난다면 바로 break 해주는 식으로 구현을 하였다.

 

2.

- 문제에 주어진 대로 경계선을 정한다면 5번으로 둘러싸여진 마름모 모양이 나올 것이고

 

1,2,3,4, 번 선거구를 범위에 맞게 넣어주어야 한다.

 

3.

- 각 선거구를 넣을 때는 1,3번 선거구는 5를 만나면 바로 다음 줄로 가고

 

2,4번은 같은 방법으로 할수 없으므로 맨 마지막부터 시작해서 5를 만나면 이전 줄로 가게 해주자

 

4

- 선거구를 넣어줄때 합도 같이 구해서 바로 차를 계산할 수 있게 해주자

 

 

코드 ( C++ )

	#include <iostream>
	#include <queue>
	#include <algorithm>
	#include <vector>
	#include <cstring>
	using namespace std;
	int a[21][21];
	int g[21][21];
	int N;
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0,0,1,-1 };
	int d[21][21];
	int BFS(int x, int y, int num)
	{
	queue<pair<int, int>> q;
	q.push({ x,y });
	d[x][y] = 0;
	int sum = a[x][y];
	while (!q.empty()) {
	int cx = q.front().first;
	int cy = q.front().second;
	q.pop();
	for (int i = 0; i < 4; ++i) {
	int nx = cx + dx[i];
	int ny = cy + dy[i];
	if (!(1 <= nx && nx <= N && 1 <= ny && ny <= N)) continue;
	if (g[nx][ny] == num && d[nx][ny] == -1) {
	sum += a[nx][ny];
	d[nx][ny] = d[x][y] + 1;
	q.push({ nx,ny });
	}
	}
	}
	return sum;
	}
	int BFS2(int x, int y, int num)
	{
	queue<pair<int, int>> q;
	q.push({ x,y });
	d[x][y] = 0;
	int sum = a[x][y];
	while (!q.empty()) {
	int cx = q.front().first;
	int cy = q.front().second;
	q.pop();
	for (int i = 0; i < 4; ++i) {
	int nx = cx + dx[i];
	int ny = cy + dy[i];
	if (!(1 <= nx && nx <= N && 1 <= ny && ny <= N)) continue;
	if ((g[nx][ny] == 5 || g[nx][ny] == 0) && d[nx][ny] == -1) {
	sum += a[nx][ny];
	d[nx][ny] = d[cx][cy] + 1;
	q.push({ nx,ny });
	}
	}
	}
	return sum;
	}
	int main()
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int total = 0;
	cin >> N;
	for (int i = 1; i <= N; ++i)
	for (int j = 1; j <= N; ++j) {
	cin >> a[i][j];
	total += a[i][j];
	}
	memset(d, -1, sizeof(d));
	int ans = 987654321;
	for (int i = 1; i <= N; ++i) {
	for (int j = 1; j <= N; ++j) {
	for (int d1 = 1; d1 <= N; ++d1) {
	for (int d2 = 1; d2 <= N; ++d2) {
	memset(g, 0, sizeof(g));
	if (i + d1 + d2 > N) break;
	if (j + d2 > N) break;
	bool check = false;
	//경계선 정하기
	for (int k = 0; k <= d1; ++k) {
	if (i + k > N || j - k < 1) {
	check = true;
	break;
	}
	g[i + k][j - k] = 5;
	}
	if (check) break;
	for (int k = 0; k <= d2; ++k) {
	if (i + k > N) {
	check = true;
	break;
	}
	if (j + k > N) {
	check = true;
	break;
	}
	g[i + k][j + k] = 5;
	}
	if (check) break;
	for (int k = 0; k <= d2; ++k) {
	if (i + d1 + k > N) {
	check = true;
	break;
	}
	if (j - d1 + k < 1) {
	check = true;
	break;
	}
	if (j - d1 + k > N) {
	check = true;
	break;
	}
	g[i + d1 + k][j - d1 + k] = 5;
	}
	if (check) break;
	for (int k = 0; k <= d1; ++k) {
	if (i + d2 + k > N) {
	check = true;
	break;
	}
	if (j + d2 - k < 1) {
	check = true;
	break;
	}
	if (j + d2 - k > N) {
	check = true;
	break;
	}
	g[i + d2 + k][j + d2 - k] = 5;
	}
	if (check) break;
	vector<int> sum(6);
	//1번 선거구
	for (int r = 1; r < i + d1; ++r)
	for (int c = 1; c <= j; ++c) {
	if (g[r][c] == 5) break;
	if (g[r][c] == 0) {
	g[r][c] = 1;
	sum[1] += a[r][c];
	}
	}
	//2번 선거구 거꾸로
	for (int r = i + d2; r >= 1; --r)
	for (int c = N; c >= j + 1; --c) {
	if (g[r][c] == 5)
	break;
	if (g[r][c] == 0) {
	g[r][c] = 2;
	sum[2] += a[r][c];
	}
	}
	//3번 선거구
	for (int r = i + d1; r <= N; ++r)
	for (int c = 1; c < j - d1 + d2; ++c) {
	if (g[r][c] == 5)
	break;
	if (g[r][c] == 0) {
	g[r][c] = 3;
	sum[3] += a[r][c];
	}
	}
	//4번 선거구 거꾸로
	for (int r = N; r >= i + d2; --r) {
	for (int c = N; c >= j - d1 + d2; --c) {
	if (g[r][c] == 5)
	break;
	if (g[r][c] == 0) {
	g[r][c] = 4;
	sum[4] += a[r][c];
	}
	}
	}
	//5번선거구의 합 전체에서 빼준다.
	sum[5] = total - sum[1] - sum[2] - sum[3] - sum[4];
	sort(sum.begin() + 1, sum.end());
	ans = min(ans, sum[5] - sum[1]);
	}
	}
	}
	}
	cout << ans << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub