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

A. 문제설명

 

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

17779번: 게리맨더링 2

문제에 대한 자세한 설명은 링크 참조

 

1. N*N 배열 크기의 땅이 존재

2. 각 배열의 엔트리를 5개의 지역구로 나누려고 함

3. 선거구를 나누는 방법은 아래와 같음

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

다음 칸은 경계선이다.
(x, y), (x+1, y-1), ..., (x+d1, y-d1)
(x, y), (x+1, y+1), ..., (x+d2, y+d2)
(x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
(x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

경계선과 경계선의 안에 포함되어있는 곳은 5번 선거구이다.
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

4. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구하라

 

B. 접근법

시뮬레이션

 

먼저 선거구를 문제조건에 규칙에 따라 모두 나누고, 각 지역구별 인구 수를 구해 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이 중 최소를 계속 업데이트

 

C. 풀이

1. 기준점과 경계를 조건에 따라 새 배열에 구함 - divide_area()

2. 각 지역구별로 경계를 따라 5개로 구역을 나눔 - color_area()

3. 각 지역구별 인구 수를 구해 벡터에 넣음

4. 벡터를 정렬하여 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이 중 최소를 구하고(get_diff()) 이를 계속 업데이트

5. 최종적으로 구해진 최소의 인구수 차이를 반환

 

D. 내 코드