[C++] 백준 17779번 게리맨더링 2

17779번: 게리맨더링 2

삼성 SW 역량 테스트 기출 문제

에 수록된 문제.

구현 / 브루트포스(완전탐색) / 시뮬레이션 문제.

처음에 조건 한줄을 잘못설정해줘서 계속 틀렸다.

반복문에서 break를 걸어주어야 하는데, continue를 써준게 틀린원인이였다.

정답률도 높은 편이고 생각한대로 구현을 잘 해주면 쉽게 맞출 수 있는 문제였다.

 

문제풀이

문제의 조건을 요약하면 다음과 같다.

• 선거구를 5개로 나눈다.
• 선거구를 나누는 것은 기준점 x, y와 길이 d1, d2를 정해서 나눠준다.
• d1은 왼쪽으로 증가하는 범위, d2는 오른쪽으로 증가하는 범위라고 생각하면 이해하기 쉽다.
• 나눈 후에, 인구가 가장 많은 도시의 인구 수 - 인구가 가장 적은 도시의 인구 수의 값이 최소가 되는 값을 구한다.

문제에 나온대로 구현해주면 된다.

 

선거구의 범위는 문제에 나와있다.

• 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
• 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
• 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
• 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

경계선의 범위 역시 문제에 나와있다.

1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

이 조건대로 구현을 해주면된다.

나같은 경우에는,

이런 그림으로 만일 선거구를 나눈다면,

X = 3, Y = 3, D1 = 1, D2 = 1이다.

 

1. 1번 선거구 인구수 구하기.

1	1	1
1	1	1
1	1	X1
	X2

맨 처음 1, 1에서 시작한다. 그리고 현재 X = 3 Y = 3이다.

1번 선거구의 열은 최대 Y까지이고, 행은 최대 X + D1 - 1까지이다.

(r, c)가 X1(X, Y)가 되기 전까지는 (i, 1) ~ (i, 3) 이런식으로 증가시켜준다.

만일 X1(X, Y)를 만났다면 그 다음은 X2가 되기 전까지 증가시켜준다.

위 상황에서는 X2를 만나기 전에 끝난다. 행이 최대 X까지 이므로,

 

2. 3번 선거구 인구수 구하기.

1	1	1
1	1	1
1	1	X1
3	X2
3	3	X3
3	3

1번 바로 아래에 3번이 있으므로 3번 선거구를 먼저 구해보겠다.

3번 행의 시작은 X + D1행에서 시작하며, 최대 N까지이다.

3번 열의 시작은 1에서 시작하며 Y - D1 + D2까지 범위이다.

처음에 X2를 만나면 그다음 경계칸 X3을 만들어준다.

만일 X3의 c좌표가 Y - D1 + D2라면, 더이상 증가시켜주지 않는다.

위 조건이 중요하다. 위에서 설명한 break문이 위 부분에서 써야한다.

 

3. 2번 선거구 인구수 구하기.

1	1	1	2	2	2
1	1	1	2	2	2
1	1	X1	2	2	2
3	X2		X4	2	2
3	3	X3
3	3

1번 인구수를 구할때와 비슷하다.

행의 범위가 1부터 X + d2이며, 열의 범위는 Y + 1부터 N까지이다.

1행부터 X4 바로 직전행까지는 2번 인구수에 추가시켜준다.

그리고 X4를 만났다면, 해당 칸은 경계선으로 만든다.

다음 경계선을 만들어줘야하는데, 어차피 2의 범위가 X4의 행에서 끝나므로 고려할 필요가 없다.

 

4. 4번 선거구 인구수 구하기.

1	1	1	2	2	2
1	1	1	2	2	2
1	1	X1	2	2	2
3	X2		X4	2	2
3	3	X3	4	4	4
3	3	4	4	4	4

4번 인구수는 행의 시작을 위에서부터할지, 아래에서부터 할지에 따라 조건을 잘 짜주면된다.

그리고 1, 2, 3의 방식과 비슷하게 구현해주면된다.

 

 

위와같은 방식의 탐색을 모든 칸에 대해서 고려해주면 된다.

N의 범위가 최대 20이므로,

모든 칸은 최대 400개가 된다.

d1, d2가 1부터 19까지 가능하다고 할 때, 한 칸마다 모든 d1, d2를 고려한다고 하면

400 * 19 * 19의 범위로 탐색이 가능하고 여기서 또 모든 칸을 고려한다고 하면 400칸을 또 탐색해야한다.

 

정말 최악의 경우 57,760,000의 시간이 걸리지만, 이정도까지는 사실 시간이 걸리지 않는다.

문제의 조건에 (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)라는 범위가 주어지고,

d1, d2에 따라 선거구를 나눌 때 모든 칸을 고려하지는 않기 때문이다.

 

이제 코드로 살펴보자.

 

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

int widthHeight;
int pointX, pointY, lengthD1, lengthD2;
int city[21][21];
int totalPopulation;
int population[6];
int ans = 40001;

사용한 STL과 변수.

memset 메서드를 사용하기위해 cstring STL을 include했다.

• widthHeight : 입력받는 N
• pointX, pointY, lengthD1, lengthD2 : 기준점 x, y와 길이 d1과 d2
• city 배열 : 각 칸의 사람 수를 정하는 것.
• totalPopulation : 모든 칸의 인구수를 합한 값.
• population 배열 : 1번 선거구 ~ 5번 선거구 까지의 인구수를 저장하는 배열
• ans : 출력하는 최소 차이의 값. 최소차이여야 하므로, 40001로 초기화해줬다.

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

	cin >> widthHeight;

	for (int i = 1; i <= widthHeight; i++) {
		for (int j = 1; j <= widthHeight; j++) {
			cin >> city[i][j];
			totalPopulation += city[i][j];
		}
	}

	for (int d1 = 1; d1 < widthHeight; d1++) {
		for (int d2 = 1; d2 < widthHeight; d2++) {
			for (int x = 1; x <= widthHeight; x++) {
				for (int y = 1; y <= widthHeight; y++) {

					if (x + d1 + d2 <= widthHeight && 1 <= y - d1 && y + d2 <= widthHeight) {

						memset(population, 0, sizeof(population));
						pointX = x;
						pointY = y;
						lengthD1 = d1;
						lengthD2 = d2;

						go();

						int largestCity = 0;
						int smallestCity = 40001;
						for (int i = 1; i <= 5; i++) {
							largestCity = max(largestCity, population[i]);
							smallestCity = min(smallestCity, population[i]);
						}

						ans = min(ans, largestCity - smallestCity);
					}

				}
			}
		}
	}

	cout << ans;

	return 0;
}

메인함수.

처음에 N을 입력받고 각 칸에 인구수를 입력받는다.

그리고 인구수를 입력받을때마다 총 인구수 변수에 더해준다.

 

그리고 4중 포문을 이용해서 모든 x, y, d1, d2를 N의 범위에 한정해서 고려해준다.

 

또한 문제의 조건에 맞는 범위라면 다음과 같은 순서로 진행된다.

1. 1 ~ 5번 선거구의 인구수를 저장하는 배열 population을 0으로 초기화한다.
2. x, y, d1, d2 변수를 전역변수에 저장한다.
3. 경계선에따라 선거구들의 인구수를 저장하는 go() 메서드를 실행한다.
4. go() 메서드가 끝나면, largestCity 변수에 인구수가 가장 큰 선거구의 인구수를, smallestCity 변수에 인구수가 가장 적은 선거구의 인구수를 넣어둔다.
5. 현재 저장중인 ans와 largestCity - smallestCity 중 더 작은 값을 ans에 저장한다.

void go() {
	int checkX = pointX;
	int checkY = pointY;
	//1번 선거구
	for (int r = 1; r < pointX + lengthD1; r++) {
		for (int c = 1; c <= checkY	; c++) {
			if (r == checkX && c == checkY) {
				checkX++;
				checkY--;
			}
			else {
				population[1] += city[r][c];
			}
		}
	}

	checkX = pointX + 1;
	checkY = pointY + 1;
	//2번 선거구
	for (int r = 1; r <= pointX + lengthD2; r++) {
		for (int c = checkY; c <= widthHeight; c++) {
			if (r == checkX && c == checkY) {
				checkX++;
				checkY++;
				continue;
			}
			else {
				population[2] += city[r][c];
			}
		}
	}

	checkX = pointX + lengthD1;
	checkY = pointY - lengthD1;
	//3번 선거구
	for (int r = pointX + lengthD1; r <= widthHeight; r++) {
		for (int c = 1; c <= checkY; c++) {
			if (r == checkX && c == checkY) {
				if (checkY != pointY - lengthD1 + lengthD2 - 1) {
					checkX++;
					checkY++;
				}
				break; // 여기 break문 중요. checkY가 계속 증가한다. 이게 틀린 이유.
			}
			else {
				population[3] += city[r][c];
			}
		}
	}

	checkX = pointX + lengthD2 + lengthD1;
	checkY = pointY + lengthD2 - lengthD1;
	//4번 선거구
	for (int r = widthHeight; r > pointX + lengthD2; r--) {
		for (int c = checkY; c <= widthHeight; c++) {
			if (r == checkX && c == checkY) {
				checkX--;
				checkY++;
				continue;
			}
			else {
				population[4] += city[r][c];
			}
		}
	}

	//5번 선거구
	population[5] = totalPopulation - population[1] - population[2] - population[3] - population[4];
}

선거구들에 인구수를 할당하는 메서드.

 

3번 선거구가 중요한데, 다른 선거구와 달리 break문이 필요하다.

각 선거구마다 checkX, checkY라는 기점을 둬서 해당 점을 만나면 다음 경계선을 할당하게한다.

3번 선거구의 경우, 열 c가 checkY까지의 범위인데 checkY를 1 더해주므로, 계속해서 열 c가 늘어날 수 있다.

따라서 break문을 써준다.

나머지는 계속 탐색하거나 범위에 상관없으므로 continue를 써준다.

 

모든 선거구를 위에서 설명한대로 인구수를 구해줬다면,

5번 선거구의 인구수는 총 인구수에서 나머지 선거구의 인구수를 빼주면 된다.

 

그리고 메인함수에서 ans를 출력한다.

 

위에서 설명한대로 break문 하나때문에 계속 틀렸습니다 를 받았다.

정답률이 높아서 그런지 반례도 잘 없었고 예시 테스트케이스들은 잘 나오는게 문제였다.

그리고 문제의 범위 내로 조건을 걸어주니 시간도 많이 줄었다.

구상을 많이 하지 않고 풀었는데, 그게 독이였던 것 같다.

앞으로는 다시 구상을 많이하고 확실한 조건을 생각하고 풀어야겠다.

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.