SW 역량테스트 - [백준] 게리맨더링 2 문제 풀이/해답/코드 (C++ / JAVA)

---

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 

---

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

해답 코드 : 

 

#include <iostream>
#include <vector>

using namespace std;

typedef struct pos {

	int row;
	int col;

}pos;


int st_r, st_c, d1, d2;
int N;

int map[20][20];
// mark vote district
int vote[20][20];
// number of people in the district
int popul[6];

int ans;

// 0 : Left, 1 : Up, 2 : Right, 3 : Down
pos vertex[4];



bool isRange(int r, int c) {

	if (r < 0 || r >= N || c < 0 || c >= N) {
		return false;
	}
	else {
		return true;
	}

}

// paint area 1
void paint_1() {
	for (int i = 0; i < vertex[0].row; i++) {
		for (int j = 0; j <= vertex[1].col; j++) {
			if (vote[i][j] == 5) {
				break;
			}
			vote[i][j] = 1;
		}
	}
}

// paint area 2
void paint_2() {
	for (int i = 0; i <= vertex[2].row; i++) {
		for (int j = N-1; j > vertex[1].col; j--) {
			if (vote[i][j] == 5) {
				break;
			}
			vote[i][j] = 2;
		}
	}
}

// paint area 3
void paint_3() {
	for (int i = vertex[0].row; i < N; i++) {
		for (int j = 0; j < vertex[3].col; j++) {
			if (vote[i][j] == 5) {
				break;
			}
			vote[i][j] = 3;
		}
	}
}

// paint area 4
void paint_4() {
	for (int i = vertex[2].row+1; i < N; i++) {
		for (int j = N-1; j >= vertex[3].col; j--) {
			if (vote[i][j] == 5) {
				break;
			}
			vote[i][j] = 4;
		}
	}
}

// paint line of area 5 and fill 0 with 5
void paint() {

	// paint lines of area 5
	// line 1
	for (int i = 0; i < d1; i++) {
		vote[vertex[0].row-i][vertex[0].col+i] = 5;
	}

	// line 2
	for (int i = 0; i < d2; i++) {
		vote[vertex[1].row+i][vertex[1].col+i] = 5;
	}
	// line 3
	for (int i = 0; i < d1; i++) {
		vote[vertex[2].row + i][vertex[2].col - i] = 5;
	}
	// line 4
	for (int i = 0; i < d2; i++) {
		vote[vertex[3].row - i][vertex[3].col - i] = 5;
	}

	paint_1();
	paint_2();
	paint_3();
	paint_4();

	// paint 0 area to 5
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (vote[i][j] == 0) {
				vote[i][j] = 5;
			}
		}
	}


}

void count() {

	int min_val = INT16_MAX, max_val = INT16_MIN;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			popul[vote[i][j]] += map[i][j];
		}
	}

	// update difference
	for (int i = 1; i < 6; i++) {
		min_val = min(min_val, popul[i]);
		max_val = max(max_val, popul[i]);
	}

	ans = min(ans, max_val - min_val);

}

// paint area 5 and call divde_1 ~ 4
void divide() {


	// pick st_r, st_c
	for (int i = 1; i < N - 1; i++) {
		for (int j = 0; j < N - 2; j++) {

			// pick d1, d2. k -> d1, l -> d2
			for (int k = 1; k < N - 1; k++) {
				for (int l = 1; l < N - 1; l++) {

					// if in range, do paint map
					if ((j + k + l) < N && (i-k) >= 0 && (i+l) < N) {
						d1 = k;
						d2 = l;

						// 0 : Left, 1 : Up, 2 : Right, 3 : Down
						vertex[0] = { i, j };
						vertex[1] = { i - d1, j + d1 };
						vertex[2] = { i - d1 + d2, j + d1 + d2 };
						vertex[3] = { i + d2, j + d2 };

						paint();

						// count number of people of each district
						// use vote[][]
						count();

						// initialize vote[][] and popul
						fill(&vote[0][0], &vote[19][20], 0);
						fill_n(&popul[0], 6, 0);

					}
					else {
						continue;
					}

				}
			}




		}
	}

}

int main() {

	cin >> N;
	ans = INT32_MAX;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
		}
	}
	
	divide();

	cout << ans << endl;

}

 

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제