[백준] 17779 게리맨더링 2

삼성 기출 게리맨터링2 문제 풀이입니다.

게리멘더링2

문제는 굉장히 직관적인 편이다. 문제에서 나온 조건 그대로 구현하면 되기 때문이다.

하지만 세세한 예외상황을 생각해보면 많이 복잡하고 어렵다는 것을 알 수 있다.

우선 최대 인구와 최소 인구의 차이가 최솟값인 것을 찾기 위해서는 DFS를 사용해야 했다. 모든 길이별로 DFS를 통해 완전탐색을 시킨 뒤 최솟값을 구하는 방식이기 때문이다.

DFS를 사용하여 각 선거구를 라벨링을 시킨 뒤 (여기에선 문제에서 나온 조건을 거의 그대로 구현하였다.) 선거구 인구수를 구해서 값을 구하였다. -> Labeling함수 참조

단, Chk함수를 통해 선거구가 될 수 없는 경우는 패스해줘야 한다. 오류가 나거나 시간이 초과될 수 있기 때문이다.

코드는 다음과 같습니다.

Source Code :

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

#define MAX 21
#define INF 987654321


int map[MAX][MAX]; // 나눌 선거구 
int Person[MAX][MAX]; // 인구수
pair<int, int> Pos[4]; // 꼭지점 위 오 왼 아
int N, Answer = INF;

int Cal(int Num) {
	int result = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (map[i][j] == Num) {
				result += Person[i][j];
			}
		}
	}
	return result;
}

bool Chk(int x,int y,int d1,int d2) {
	if (x + d1 + d2 > N || x > x + d1 + d2) return false;
	if (y - d1 > y || y - d1 < 1) return false;
	if (y > y + d2) return false;
	if (y + d2 > N)return false;

	return true;
}


void Labeling(int x,int y,int d1,int d2) {

	// Pos[0] up Pos[1] Right Pos[2] Left Pos[3] Down

	// 1
	int cnt = 0;
	for (int i = 1; i < Pos[2].first; i++) {
		if (i >= Pos[0].first) cnt++;
		for (int j = 1; j <= Pos[0].second - cnt; j++) {
			map[i][j] = 1;
		}
	}

	// 2
	cnt = 1;
	for (int i = 1; i <= Pos[1].first; i++) {
		if (i > Pos[0].first) cnt++;
		for (int j = Pos[0].second + cnt; j <= N; j++) {
			map[i][j] = 2;
		}
	}

	//3
	cnt = 0;

	for (int i = N; i >= Pos[2].first; i--) {
		if (i < Pos[3].first) cnt++;
		for (int j = 1; j < Pos[3].second - cnt; j++) {
			map[i][j] = 3;
		}
	}

	//4
	cnt = 0;
	for (int i = N; i > Pos[1].first; i--) {
		if (i <= Pos[3].first) cnt++;
		for (int j = Pos[3].second+cnt; j <= N; j++) {
			map[i][j] = 4;
		}
	}
}

void solve(int x, int y) { // 기준점 x, y
	
	vector<int> Vote; // 인구수, 선거구
	
	for (int d1 = 1; d1 <= y; d1++) { // d1 d2 길이
		for (int d2 = 1; d2 < N; d2++) {
			
			if (Chk(x, y, d1, d2)) {
				Pos[0].first = x;
				Pos[0].second = y;
				Pos[1].first = x + d2;
				Pos[1].second = y + d2;
				Pos[2].first = x + d1;
				Pos[2].second = y - d2;
				Pos[3].first = x + d1 + d2;
				Pos[3].second = y - d1 + d2;
				Vote.clear();
				for (int i = 1; i <= N; i++) {
					for (int j = 1; j <= N; j++) {
						map[i][j] = 5;
					}
				}

				Labeling(x, y, d1, d2);

				for (int i = 1; i <= 5; i++) {
					Vote.push_back(Cal(i));
				}

				sort(Vote.begin(), Vote.end());

				Answer = min(Answer, Vote[4] - Vote[0]);
			}
		}
	}

}

int main() {
	cin >> N;

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

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			solve(i, j);
		}
	}

	cout << Answer;

	system("pause");
	return 0;
}

• 혹시 잘못된 부분이 있다면 댓글달아주세요! 감사합니당.

소스코드

이 외에도 제가 푼 문제들 소스코드는 다음 링크에 있습니다!!! 알고리즘 문제풀이