17779. 게리맨더링 2 문제 바로가기
해결 방법
구역을 나누며 선거구에 따른 인구수를 바로 구하고 싶었으나 구역 나누는 것이 헷갈려서 test라는 리스트에 구역을 표시하고 test를 돌며 인구수를 구했습니다 :)
입력을 받은 뒤 가능한 기준점과 경계 길이를 4중 포문을 통해 뽑아낸다.
devide 함수를 통해 모든 경우를 완전 탐색하며 가장 많은 선거구와 가장 적은 선거구의 인구 차이 최솟값을 구한다.test라는 리스트에 경계를 먼저 표시한다.
test에 1번부터 4번까지의 선거구를 표시한다.
1 2 3 4 5 6 7 8 9 10 11
예를 들면 N = 6 이고 devide(1, 1, 1, 2)인 경우 test는 다음과 같다. devide(1, 1, 1, 2) : (1, 1) 기준점, d1: 1, d2: 2 test = [ [1, 1, 2, 2, 2, 2] [1, 5, 2, 2, 2, 2] [5, 0, 5, 2, 2, 2] [3, 5, 0, 5, 2, 2] [3, 3, 5, 4, 4, 4] [3, 3, 4, 4, 4, 4] ]
test를 통해 vote라는 리스트에 해당 구역별 인구수를 구한다.
(vote 리스트는 [0] * 5 로 초기화 되어있으며 첫번째 인덱스는 1번 선거구 인구를 다음 인덱스엔 2번 선거구 인구, 이런식으로 저장된다.)
이때 test 값이 5또는 0 인 경우 vote인덱스 마지막에 더해준다.
vote 값에 max 와 min 을 빼어 구하고자하는 선거구 인구차이를 구하며 최솟값을 구해준다.
구현한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def divide(y, x, d1, d2):
global gap
test = [[0] * N for _ in range(N)] # 선거구 표시할 리스트
## 1. 경계선 만들기
for i in range(d1 + 1):
test[y + i][x - i] = 5
test[y + d2 + i][x + d2 - i] = 5
for j in range(1, d2 + 1):
test[y + j][x + j] = 5
test[y + d1 + j][x - d1 + j] = 5
## 2. 선거구 나누기
# 1번
for i1 in range(y + d1):
for j1 in range(x + 1):
if test[i1][j1] == 5: break
test[i1][j1] = 1
# 2번
for i2 in range(y + d2 + 1):
for j2 in range(N - 1, x , -1):
if test[i2][j2] == 5: break
test[i2][j2] = 2
# 3번
for i3 in range(y + d1, N):
for j3 in range(x - d1 + d2):
if test[i3][j3] == 5: break
test[i3][j3] = 3
# 4번
for i4 in range(y + d2 + 1, N):
for j4 in range(N - 1, x - d1 + d2 - 1, -1):
if test[i4][j4] == 5: break
test[i4][j4] = 4
## 3. 선거구에 따른 인구 수를 vote에 저장하기
vote = [0] * 5
for li in range(N):
for lj in range(N):
if test[li][lj] == 0: # 0 인 경우 5 선거구에 속하기 때문
vote[4] += area[li][lj]
else:
vote[test[li][lj] - 1] += area[li][lj]
temp_gap = max(vote) - min(vote) # 가장 많은 선거구와 가장 적은 선거구 차이 구하기
# 최솟값인 경우 gap에 저장하기
if gap > temp_gap:
gap = temp_gap
N = int(input())
area = [list(map(int, input().split())) for _ in range(N)]
gap = float('inf')
for y in range(N - 2):
for x in range(1, N - 1):
for d1 in range(1, x + 1):
for d2 in range(1, N - x):
if y + d1 + d2 >= N:
break
# 가능한 모든 기준점과 경계 길이 탐색
divide(y, x, d1, d2)
print(gap)