백준 17779 게리맨더링 2 C++

2023. 10. 2. 18:42ㆍ알고리즘문제 풀이/백준

문제

재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.

재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.

선거구를 나누는 방법은 다음과 같다.

  1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
  2. 다음 칸은 경계선이다.
    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)
  3. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
  4. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
    • 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

아래는 크기가 7×7인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

     
x = 2, y = 4, d1 = 2, d2 = 2 x = 2, y = 5, d1 = 3, d2 = 2 x = 4, y = 3, d1 = 1, d2 = 1

구역 (r, c)의 인구는 A[r][c]이고, 선거구의 인구는 선거구에 포함된 구역의 인구를 모두 합한 값이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구해보자.

입력

첫째 줄에 재현시의 크기 N이 주어진다.

둘째 줄부터 N개의 줄에 N개의 정수가 주어진다. r행 c열의 정수는 A[r][c]를 의미한다.

출력

첫째 줄에 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 출력한다.

제한

  • 5 ≤ N ≤ 20
  • 1 ≤ A[r][c] ≤ 100

알고리즘 분류

풀이

입력 → 기준점과 경계선 정하기 →각각의 경우에 따라 선거구 나누기 → 가장 많은 선거구와 가장 적은 선거구의 인구 차이 구하기 → 선거구 나누는 방법 중에서 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값 출력

입력

N이 최대 20이고 r행 c열에 해당하는 r과 c는 1부터 시작한다.

이차원 배열 A는 0부터 순서를 매기므로 MAX를 21로 잡아준다.

#define MAX 21
int A[MAX][MAX];
int N;

int main() {
	cin >> N;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			cin >> A[r][c];
		}
	}
}

기준점과 경계 정하고 각각의 case를 모두 실행해보기

  1. 기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)

가능한 범위

1 ≤ x ≤ N

d1 ≥1, d2≥1, 1≤y-d1, y+d2 ≤N → 2 ≤ 1+d1 ≤ y ≤ N-d2 ≤ N-1 → 2≤y≤N-1

d1≥1, 1≤y-d1 → 1 ≤d1 ≤y-1

d2≥1, y+d2≤N → 1 ≤d2 ≤N-y

x+d1+d2≤N

각 기준점과 경계에 해당하는 선거구 나누고 가장 많은 선거구와 가장 적은 선거구의 인구 차이를 구하는 과정은 divde_election_area(x,y,d1,d2)를 통해 구한다.

	//d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N
	for (int x = 1; x <= N; x++) {
		for (int y = 2; y <= N-1; y++) {
			for (int d1 = 1; d1 <= y - 1; d1++) {
				for (int d2 = 1; d2 <= N - y; d2++) {
					if (x + d1 + d2 <= N) {
						divide_election_area(x, y, d1, d2);
					}
				}
			}
		}
	}

void divde_election_area(int x,int y,int d1,int d2)

각 기준점과 경계에 해당하는 가장 많은 선거구와 가장 적은 선거구의 인구 차이를 구하는 과정

선거구 구하기: 2~4 과정

  1. 다음 칸은 경계선이다. x좌표를 r, y좌표를 c로 나타낸다면 각각의 경계선을 직선의 방정식으로 나타낼 수 있다.
    1. (x, y), (x+1, y-1), ..., (x+d1, y-d1) → r+c = x+y
    2. (x, y), (x+1, y+1), ..., (x+d2, y+d2) → r-c = x-y
    3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2) → r-c=x-y+2*d1
    4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)→ r+c = x+y+2*d2
  2. 경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.

a,b,c,d의 경계선이나 경계선 안쪽의 범위는

x+y ≤r+c≤x+y+2d2 , x-y≤r-c≤x-y+2d1

이에 해당하는 곳은 5번 선거구이다.

5번 선거구에 해당하는 인구를 더해줘서 5번 선거구의 인구를 구한다.

//int election_area[MAX][MAX]; //선거구
void divide_election_area(int x, int y, int d1, int d2) {
	int election_area_5 = 0;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			if (r + c >= x + y && r - c >= x - y && r-c <= x - y + 2 * d1 && r +  c <= x + y + 2 * d2) {
				//경계선이나 경계선 내부에 포함하는 경우
				election_area_5 += A[r][c];
        //선거구 5이고 거기에 해당하는 인구의 수를 더해준다.
			}
		}
	}
}
  1. 5번 선거구에 포함되지 않은 구역 (r, c)의 선거구 번호는 다음 기준을 따른다.
    • 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y → r < x+d1, c ≤ y
    • 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N → r ≤ x+d2, y < c
    • 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2 → x+d1 ≤ r , c < y-d1+d2
    • 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N → x+d2 < r , y-d1+d2 ≤ c

각각의 선거구에 해당하는 인구를 더해줘서 각각의 선거구의 인구를 구한다.

void divide_election_area(int x, int y, int d1, int d2) {
	int election_area_1 = 0;
	int election_area_2 = 0;
	int election_area_3 = 0;
	int election_area_4 = 0;
	int election_area_5 = 0;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			if (r + c >= x + y && r - c >= x - y && r-c <= x - y + 2 * d1 && r +  c <= x + y + 2 * d2) {
				//election_area[r][c] = 5;
				election_area_5 += A[r][c];
			}
			else if (r < x + d1 && c <= y) {
				//election_area[r][c] = 1;
				election_area_1 += A[r][c];
				//선거구 1이고 거기에 해당하는 인구의 수를 더해준다.
			}
			else if (r <= x + d2 && y < c) {
				//election_area[r][c] = 2;
				election_area_2 += A[r][c];
				//선거구 2이고 거기에 해당하는 인구의 수를 더해준다.
			}
			else if (x + d1 <= r && c < y - d1+d2) {
				//election_area[r][c] = 3;
				election_area_3 += A[r][c];
				//선거구 3이고 거기에 해당하는 인구의 수를 더해준다.
			}
			else if (x + d2 < r && y - d1 + d2 <= c) {
				//election_area[r][c] = 4;
				election_area_4 += A[r][c];
				//선거구 4이고 거기에 해당하는 인구의 수를 더해준다.
			}
		}
	}
}

가장 많은 선거구와 가장 적은 선거구의 인구 차이 구하기

각각 선거구의 인구를 배열에 넣은 후

#include <algorithm>을 추가한 뒤

sort함수를 이용해서 오름차순 정렬한다.

그 후 마지막항(최댓값)-첫번째항(최솟값) 을 통해 가장 많은 선거구와 가장 적은 선거구의 인구 차이를 구한다

이 값(election_area_population[4] - election_area_population[0])이 기존에 구한 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값(min_difference)보다 적은 경우에 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값(min_difference)이 된다.

(min_differnce의 초기값은 INF(=987654321)이다.)

#define INF 987654321	
int min_difference = INF;
void divide_election_area(int x, int y, int d1, int d2) {
   
	int election_area_population[5] = {election_area_1,election_area_2,election_area_3,election_area_4, election_area_5 };
	sort(election_area_population, election_area_population + 5);
	min_difference = min(min_difference, election_area_population[4] - election_area_population[0]);
}

출력

선거구 나누는 방법 중에서 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값 출력한다.

cout << min_difference;

전체코드문제

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 21
#define INF 987654321

int A[MAX][MAX];
int N;
//int election_area[MAX][MAX]; //선거구
int min_difference = INF;


void divide_election_area(int x, int y, int d1, int d2) {
	int election_area_1 = 0;
	int election_area_2 = 0;
	int election_area_3 = 0;
	int election_area_4 = 0;
	int election_area_5 = 0;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			if (r + c >= x + y && r - c >= x - y && r-c <= x - y + 2 * d1 && r +  c <= x + y + 2 * d2) {
				//election_area[r][c] = 5;
				election_area_5 += A[r][c];
			}
			else if (r < x + d1 && c <= y) {
				//election_area[r][c] = 1;
				election_area_1 += A[r][c];
			}
			else if (r <= x + d2 && y < c) {
				//election_area[r][c] = 2;
				election_area_2 += A[r][c];
			}
			else if (x + d1 <= r && c < y - d1+d2) {
				//election_area[r][c] = 3;
				election_area_3 += A[r][c];
			}
			else if (x + d2 < r && y - d1 + d2 <= c) {
				//election_area[r][c] = 4;
				election_area_4 += A[r][c];
			}
		}
	}
	
	min_difference = min(min_difference, election_area_population[4] - election_area_population[0]);

}

int main() {
	cin >> N;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			cin >> A[r][c];
		}
	}

	//d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N
	for (int x = 1; x <= N; x++) {
		for (int y = 2; y <= N-1; y++) {
			for (int d1 = 1; d1 <= y - 1; d1++) {
				for (int d2 = 1; d2 <= N - y; d2++) {
					if (x + d1 + d2 <= N) {
						divide_election_area(x, y, d1, d2);
					}
				}
			}
		}
	}

	cout << min_difference;
	return 0;
}

'알고리즘문제 풀이 > 백준' 카테고리의 다른 글

백준 17837 새로운 게임 2 C++  (0) 2023.10.09
백준 17825 주사위 윷놀이 C++  (1) 2023.10.09
백준 17496 스타후르츠 C++  (1) 2023.10.02
백준 17256 달달함이 넘쳐흘러 C++  (1) 2023.10.02
백준 17144 미세먼지 안녕 C++  (0) 2023.10.02

관련글

티스토리툴바