백준 17779번 _ 게리맨더링 2

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

17779번: 게리맨더링 2

풀이방법

 이 문제는 주어진 범위 그대로 5 선거구의 경계선을 그어주고 풀면 풀이가 쉽다. 그러므로 내 코드를 참조하여 풀이시 주의할 사항만 서술하겠다.

 위 그림의 화살표는 조회하는 방향이다. 빨간색은 1, 3 선거구, 파랑색은 2, 4 선거구 이다. 이렇게 조회해야하는 이유는 간단하다. 

 우리는 5선거구의 경계만 표시했다. 그러므로 2, 4 선거구가 빨간색 화살표같은 조회방향을 갖는다면 5선거구도 자신의 선거구로 착각하고 값에 추가할수 있다.

---

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

int map[22][22];
bool visit[22][22];
int tmpMap[22][22];
int N;
int totalVoter;

void print()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
			cout << tmpMap[i][j] << ' ';
		cout << endl;
	}
}

void visitInit()
{
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			visit[i][j] = false;
}

void Input()
{
	cin >> N;
	int value;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> value;
			map[i][j] = value;
			totalVoter += value;
		}
	}
}

bool isInMap(int num1, int num2)
{
	if (num1 > 0 && num2 > 0 && num1 <= N && num2 <= N)
		return true;
	return false;
}

bool isPossible(int x, int y, int d1, int d2)
{
	if (isInMap(x, y) && isInMap(x + d1, y - d1) && isInMap(x + d2, y + d2) && isInMap(x + d1 + d2, y + d2 - d1))
		return true;
	return false;
}

int checkElectionStatus(int x, int y, int d1, int d2)
{
	//경계선 그리기
	for (int i = 0; i <= d1; i++)
	{
		visit[x + i][y - i] = true;
		visit[x + d2 + i][y + d2 - i] = true;
	}
	for (int i = 0; i <= d2; i++)
	{
		visit[x + i][y + i] = true;
		visit[x + d1 + i][y - d1 + i] = true;
	}

	int minValue = INT_MAX;
	int maxValue = 0;
	int cnt[] = { 0,0,0,0,0,0 };

	//1번
	for (int i = 1; i < x + d1; i++)
		for (int j = 1; j <= y; j++)
		{
			if (visit[i][j] == true)
				break;
			cnt[1] += map[i][j];
		}
	//2번
	for (int i = 1; i <= x + d2; i++)
		for (int j = N; j > y; j--)
		{
			if (visit[i][j] == true)
				break;
			cnt[2] += map[i][j];
		}
	//3번
	for (int i = x + d1; i <= N; i++)
		for (int j = 1; j < y - d1 + d2; j++)
		{
			if (visit[i][j] == true)
				break;
			cnt[3] += map[i][j];
		}
	//4번
	for (int i = x + d2 + 1; i <= N; i++)
		for (int j = N; j >=y-d1+d2; j--)
		{
			if (visit[i][j] == true)
				break;
			cnt[4] += map[i][j];
		}
	//5번
	cnt[5] = totalVoter;
	for (int i = 1; i <= 4; i++)
		cnt[5] -= cnt[i];

	for (int i = 1; i <= 5; i++)
	{
		minValue = min(minValue, cnt[i]);
		maxValue = max(maxValue, cnt[i]);
	}
	visitInit();
	return maxValue - minValue;
}

void solve()
{
	int answer = INT_MAX;
	//select x, y, d1, d2
	for (int d1 = 1; d1 <= N; d1++)
		for (int d2 = 1; d2 <= N; d2++)
			for (int x = 1; x + d1 + d2 <= N; x++)
				for (int y =1; y + d2 <= N; y++)
				{
					if (!(y - d1 >= 1))
						continue;
					if (isPossible(x, y, d1, d2) == false)
						continue;
					//check election status
					answer = min(checkElectionStatus(x, y, d1, d2), answer);
				}

	cout << answer;
}

int main()
{
	Input();
	solve();
	return 0;
}

 

---

후기

요즘 문제 풀기가 싫다..