17779번 게리맨더링2

내 머리 속에 삼성 코테 = bfs + dfs + 빡구현이라서, 오히려 더 어렵게 돌아돌아 풀었다.

70분 정도 걸렸는데, 시험장 가면 떨려서 더 걸릴텐데 벌써 걱정된다. 힝;ㅜ

 

컴공이 아닌 걸 극복하려고 문제를 무작정 많이 푸는 스타일이지, 엄청 효율적으로 사고하는 편이 아니다.

그래서 구현같은 경우는 주어진 순서를 따라서 차근차근 하나하나씩 함수를 짠다. 

 

내 코드 

 

choice standard 라는 4중 포문으로 기준점 x,y와 길이 d1,d2를 선택한 다음,  color_five 함수로 경계선을 -1로 체크해주었다. 그 다음 왼쪽, 오른쪽을 나눠서 divide 함수를 통해서 1,2,3,4 구역별로 정해주었다.

마지막으로 color_inner이라는 bfs문을 돌면서 경계선 혹은 경계선 내부면 5로 체크를 해주었다. 

이 후 local_pop에 해당 숫자에 맞게 저장된 숫자들을 비교

이렇게하면 20ms 정도 나온다.

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
// 4 : 20 - 
int x, y, d1, d2, n, min_diff = 987654321;
int map[21][21] = { 0 };
int temp[21][21] = { 0 };
int local_pop[6] = { 0 };
int dr[] = { -1,1,0,0 };
int dc[] = { 0,0,-1,1 };

void divide(int num, int sr, int sc, int er, int ec) {
	// num = 1. sr =1 . sc = 1. sr = x + d1 , sc = y
	if (num == 1 || num == 3) {
		for (int i = sr; i <= er; i++) {
			bool stop = false;
			for (int j = sc; j <= ec; j++) {
				if (stop) continue;
				if (stop == false && temp[i][j] == -1) stop = true;
				else {
					temp[i][j] = num;
					local_pop[num] += map[i][j];
				}
			}
		}
	}
	if (num == 2 || num == 4) {
		for (int i = sr; i <= er; i++) {
			bool stop = false;
			for (int j = ec; j >= sc; j--) {
				if (stop) continue;
				if (stop == false && temp[i][j] == -1) stop = true;
				else {
					temp[i][j] = num;
					local_pop[num] += map[i][j];
				}
			}
		}
	}
}

bool check(int r, int c) {
	if (0 < r && r < n + 1 && 0 < c && c < n + 1 && (temp[r][c] == 0 || temp[r][c] == -1)) return true;
	return false;
}

void color_five() {
	for (int i = 0; i <= d1; i++) temp[x + i][y - i] = -1;
	for (int i = 0; i <= d2; i++) temp[x + i][y + i] = -1;
	for (int i = 0; i <= d2; i++) temp[x + d1 + i][y - d1 + i] = -1;
	for (int i = 0; i <= d1; i++) temp[x + d2 + i][y + d2 - i] = -1;
}

void color_inner() {
	////////경계선 내부 개수 세기
	queue<pair<int, int>>q;
	q.push({ x,y });
	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (check(nr, nc)) {
				temp[nr][nc] = 5;
				local_pop[5] += map[nr][nc];
				q.push({ nr,nc });
			}
		}
	}
}

void choice_standard() { //기준점과 길이를 선택해야함
	for (int i = 1; i <= n; i++) {
		for (int j = 2; j <= n; j++) {
			//x,y 기준점 설정
			for (int a = 1; a < n-1; a++) {
				for (int b = 1; b < n-1; b++) {
				//경계의 길이 설정
					if (i + a + b <= n && j - a >= 1 && j + b <= n) {
						x = i, y = j, d1 = a, d2 = b;
						memset(temp, 0, sizeof(temp));
						memset(local_pop, 0, sizeof(local_pop));
						color_five();
						divide(1, 1, 1, x + d1-1, y);
						divide(2, 1, y + 1, x + d2, n);
						divide(3, x + d1, 1, n, y - d1 + d2 - 1);
						divide(4, x + d2 + 1, y - d1 + d2, n, n);
						color_inner();
						int max_pop = *max_element(local_pop + 1, local_pop + 6);
						int min_pop = *min_element(local_pop + 1, local_pop + 6);
						int diff = max_pop - min_pop;
						min_diff = min(min_diff, diff);
						}
					}
				}
			}
		}
}


int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) cin >> map[i+1][j+1]; //1부터 시작하게 맞춰주자
	}
	choice_standard();
	cout << min_diff;
}

 

이렇게 하는 게 최선이 아닐 거 같아서 다른 사람들 코드를 좀 살펴봤다. 

velog명이 미친감자 같다.

이분은 16ms가 나오셨다는데,,, 속도도 속도지만 정말 간단하게? 푸셨다 ㅜㅜ 난 너무 돌아 풀었다. 

합을 구하는 거니까 5번은 그냥 total 합에서 나머지 1,2,3,4를 빼면 구해지는 것인데,,,굳이 bfs까지,,,? ㅜㅜ 

 

우선 기준점을 선택하는 4중 for문 먼저 보면 

아 for문안에도 d1 <= y-1 && d1 <= N-x-1 이런 식으로 쓸 수 있구나,,, 

이렇게 되면 굳이 전체 범위를 돌면서 if문으로 확인하지 않아도 되니까 더 빨리질 거 같긴하다.

nt minDiff() {
	int res = INF;

	for (int x = 1; x <= N - 2; x++) {
		for (int y = 2; y <= N - 1; y++) {
			for (int d1 = 1; d1 <= y - 1 && d1 <= N - x - 1; d1++) {
				for (int d2 = 1; d2 <= N - y && d2 <= N - x - 1; d2++) {
					res = min(res, diff(x, y, d1, d2));
				}
			}
		}
	}

	return res;
}

 

굳이 경계선을 설정?할 필요 없이 경계점을 기준으로 하는 구역만의 범위 내에 있으면 된다,,,ㅜㅜ

int diff(int x, int y, int d1, int d2) {
	vector<int> population(5, 0);

	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			//1번 선거구
			if (r < x + d1 && c <= y && !(r >= x && c >= y - (r - x))) {
				population[0] += map[r][c];
			}
			//2번 선거구
			else if (r <= x + d2 && c > y && !(r >= x && c <= y + (r - x))) {
				population[1] += map[r][c];
			}
			//3번 선거구
			else if (r >= x + d1 && c < y - d1 + d2 && !(r <= x + d1 + d2 && c >= (y - d1 + d2 - (x + d1 + d2 - r)))) {
				population[2] += map[r][c];
			}
			//4번 선거구
			else if (r > x + d2 && c >= y - d1 + d2 && !(r <= x + d1 + d2 && c <= (y - d1 + d2 + (x + d1 + d2 - r)))) {
				population[3] += map[r][c];
			}
			//5번 선거구
			else {
				population[4] += map[r][c];
			}
		}
	}

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

	return population[4] - population[0];
}