백준 17779번: 게리맨더링 2 (C++)

문제 링크 : www.acmicpc.net/problem/17779

 

 

<전체적인 알고리즘>

1. 이차원 배열을 순차 탐색하며 기준점과 d1,d2를 정해준다. 

2. 기준점부터 왼쪽으로 내려가는 좌표와 오른쪽으로 내려가는 좌표를 나누어서 탐색한다.

3. 행마다,,, 1~lefty 는 왼쪽 영역, lefty ~ righty 는 가운데 영역,  righty ~ n 까지는 오른쪽 영역 으로 구분해서 채운다.

    (아랫부분일때는 증가방식을 반대로 한다.)

4. 5영역의 경계선이 없는 행들도 다 채워준다.

5. 1,2,3,4를 반복한다.

 

 

 

<전체 코드>

#include<iostream>
#include<algorithm>
using namespace std;

int map[22][22];
int n;
int go_left[2] = { 1,-1 };
int go_right[2] = { 1,1 };

int result_gap(int(&tmp)[22][22])   //영역들 중 최대값과 최소값 차이 구하기
{
	int area[5] = { 0,0,0,0,0 };
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int num = tmp[i][j];
			area[num - 1] += map[i][j];    //구역마다 인원 합하기
		}
	}
	sort(area, area + 5);
	return area[4] - area[0];    //최대 영역과 최소 영역 차이 반환
}

int make_area(int x, int y, int d1, int d2)
{
	int tmp[22][22];
	int leftx = x;
	int lefty = y;
	int rightx = x;
	int righty = y;
	tmp[x][y] = 5;
	bool left_below_area = false;
	bool right_below_area = false;

	while (1)
	{
		for (int i = 1; i < lefty; i++)    // 왼쪽 경계선의 왼쪽부분 영역 채우기
		{
			if (leftx < x + d1) tmp[leftx][i] = 1; // 윗부분 이면 1로
			else tmp[leftx][i] = 3;  //아랫부분이면 3으로	
		}

		for (int i = lefty; i <= righty; i++) tmp[rightx][i] = 5; //경계선 가운데는 5로

		for (int i = righty + 1; i <= n; i++)//오른쪽 경계선의 오른쪽부분 전부 2로
		{
			if (rightx <= x + d2)tmp[rightx][i] = 2;  //오른쪽 윗부분이면 2
			else tmp[rightx][i] = 4;  //오른쪽 아랫부분은 4
		}
		if (leftx == x + d1 + d2)break;  

		if (leftx < x + d1)   //위부분은 왼쪽으로 증가
		{
			leftx += go_left[0];
			lefty += go_left[1];
		}
		else                        //아랫부분은 오른쪽으로 증가
		{
			leftx += go_right[0];
			lefty += go_right[1];
		}
		if (rightx < x + d2)          //윗부분은 오른쪽으로 증가
		{
			rightx += go_right[0];
			righty += go_right[1];
		}
		else                         //아랫부분은 왼쪽으로 증가
		{
			rightx += go_left[0];
			righty += go_left[1];
		}
	}

	for (int i = x - 1; i >= 1; i--)  //5가 없는 윗행들 나머지 채워주기
	{
		for (int j = 1; j <= y; j++)tmp[i][j] = 1;

		for (int j = y + 1; j <= n; j++)tmp[i][j] = 2;
	}

	for (int i = leftx + 1; i <= n; i++) //5가 없는 아랫행들 나머지 채워주기
	{
		for (int j = 1; j < lefty; j++)tmp[i][j] = 3;

		for (int j = lefty; j <= n; j++) tmp[i][j] = 4;
	}

	int result = result_gap(tmp);  //차이 구하기

	return result;
}

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

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

	int minn = 987654321;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			for (int d1 = 1;; d1++)
			{
				if (j - d1 < 1)break;  //왼쪽 범위 넘어가면 break
				for (int d2 = 1;; d2++)
				{
					if (i + d1 + d2 > n)break; //바닥 넘어가면 break
					if (j + d2 > n)break;  //오른쪽 범위 넘어가면 break
					minn = min(minn, make_area(i, j, d1, d2));   //영역 나누기
				}
			}
		}
	}
	cout << minn;

	return 0;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.