[Algorithm][C++] BOJ 17779 게리맨더링2

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

17779번: 게리맨더링 2

 

풀이 핵심

1. Bruth Force 문제 

 

2. for 문으로 완전 탐색 진행

 

3. calPop 함수를 통해 인구수의 최대 최소 차 계산 4중 for 문으로 기준 점 (x, y), d1, d2를 변경 시켜 가며 체크한다. 이 때 다음과 같은 조건을 만족한 경우에만 calPop 함수가 실행 될 수 있도록 한다 (OutOfBound 가 발생하지 않게 하기 위해)

    (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)

 

4. 미리 입력을 받을 때 인구의 총 합을 sum 변수에 계산해 둔다. calPop 함수를 시작하면 pop 배열을 만들어 0, 0, 0, 0, sum 으로 초기화 한다. 그리고 map의 크기와 같은 check 배열을 만들고 check 배열에 경계 부분만 5로 표시한다.

 

5.  아래 그림과 같이 1, 3 구역은 열 방향 진행 시 열이 증가하는 방향으로 for 문을 구성하고 2, 4 구역은 열 방향 진행 시 열이 감소하는 방향으로 for 문을 구성한다. 그리고 경계 구역 (check배열에 5가 표시된 영역)을 만나면 열 방향으로 진행 중인 for 문을 중단 한다. 행 방향은 모두 증가하는 방향으로 for문을 구성한다. for 문을 돌면서 각 구역 (1,2,3,4)의 인구를 pop 배열의 0,1,2,3 인덱스에 각각 저장한다. 그 뒤 pop[4] 에는 이미 총 인구 수가 저장 되어 있으므로 pop[0], pop[1], pop[2], pop[3] 의 인구수를 빼준다. (sum - 1,2,3,4 구역 인구 = 5 구역의 인구 수)

예시

 

6. pop 배열은 요소가 5개 뿐이 므로 bubble 정렬로 간단하게 정렬 한다 (min이 0번 요소, max가 4번 요소).

 

7. pop[4] - pop[0] 을 return 한다. (max - min 값 return)

 

8. calPop으로 부터 구한 값이 ans 보다 작으면 ans에 저장한다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N;
int map[21][21];
int sum;

int calPop(int x, int y, int d1, int d2) {
	int pop[5] = { 0,0,0,0,sum }; // 1,2,3,4,5 구역 인구 담을 배열
	int check[21][21] = { 0, }; // 경계 표현 하기 위한 배열
    // 경계 표현
	for (int r = x, c = y; r <= x + d1 && c >= y - d1; r++, c--) check[r][c] = 5;
	for (int r = x, c = y; r <= x + d2 && c <= y + d2; r++, c++) check[r][c] = 5;
	for (int r = x + d1, c = y - d1; r <= x + d1 + d2 && c <= y - d1 + d2; r++, c++) check[r][c] = 5;
	for (int r = x + d2, c = y + d2; r <= x + d1 + d2 && c >= y + d2 - d1; r++, c--) check[r][c] = 5;
	
    // 1번 구역 열 진행 방향 오른쪽
	for (int r = 1; r < x + d1; r++) {
		for (int c = 1; c <= y; c++) {
			if (check[r][c] == 5) break; // 경계를 만나면 break;
			pop[0] += map[r][c];
		}
	}
    // 2번 구역 열 진행 방향 왼쪽
	for (int r = 1; r <= x + d2; r++) {
		for (int c = N; c >= y + 1; c--) {
			if (check[r][c] == 5) break; // 경계를 만나면 break;
			pop[1] += map[r][c];
		}
	}
    // 3번 구역 열 진행 방향 오른쪽
	for (int r = x + d1; r <= N; r++) {
		for (int c = 1; c < y - d1 + d2; c++) {
			if (check[r][c] == 5) break; // 경계를 만나면 break;
			pop[2] += map[r][c];
		}
	}
    // 4번 구역 열 진행 방향 왼쪽
	for (int r = x + d2 + 1; r <= N; r++) {
		for (int c = N; c >= y - d1 + d2; c--) {
			if (check[r][c] == 5) break; // 경계를 만나면 break;
			pop[3] += map[r][c];
		}
	}
    
	// 5번 구역은 1,2,3,4를 sum에 빼서 구한다
	pop[4] -= (pop[0] + pop[1] + pop[2] + pop[3]);
    
	// 버블 정렬
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5 - i - 1; j++) {
			if (pop[j] > pop[j + 1]) {
				int tmp = pop[j];
				pop[j] = pop[j + 1];
				pop[j + 1] = tmp;
			}
		}
	}

	// max - min 값 return
	return pop[4] - pop[0];
}

int main() {
	int ret = 20 * 20 * 100;
    // 입 력
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
			sum += map[i][j]; // 미리 인구 총합을 계산
		}
	}
	for (int x = 1; x <= N; x++) {
		for (int y = 1; y <= N; y++) {
			for (int d1 = 1; d1 <= N; d1++) {
				for (int d2 = 1; d2 <= N; d2++) {
                // 조건을 만족할 경우만 calPop 함수 실행 (OutofBound 방지)
					if (x < x + d1 + d2 && x + d1 + d2 <= N && \
						1 <= y - d1 && y - d1 < y&&y < y + d2 &&\
						y + d2 <= N) {
						int tmp = calPop(x, y, d1, d2);
						if (tmp < ret) ret = tmp;
					}
				}
			}
		}
	}
    // 출 력
	printf("%d", ret);
	return 0;
}

 

 

아쉬운 점

1. 문제에 조건들이 복잡해서 특정 기준점(x, y) 일 때 d1, d2가 될 수 있는 최대 최소를 구하는 것이 복잡해 보였다.

2. 따라서 단순히 생각하기 위해 문제의 조건에 부합 할 경우에만 calPop 함수가 실행되도록 하여 OutOfBound가 발생하지 않도록 했다.

3. 처음에는 문제에 제시된 변수로 코드를 작성하지 않아 조건을 입력하는데 실수가 있었다.

4. 다음부턴 꼭 문제에 제시된 변수로 코드를 작성해야겠다.

5. 어렵지 않은 Bruth Force 문제였다. (재귀 함수로는 어떻게 구현 할 수 있을까?)