게리맨더링 2

게리맨더링 2

문제

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

재현시는 크기가 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인 재현시를 다섯 개의 선거구로 나눈 방법의 예시이다.

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

입력

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

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

출력

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

제한

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

예제 입력 1

6
1 2 3 4 1 6
7 8 9 1 4 2
2 3 4 1 1 3
6 6 6 6 9 4
9 1 9 1 9 5
1 1 1 1 9 9

예제 출력 1

18

예제 입력 2

6
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5
5 5 5 5 5 5

예제 출력 2

20

예제 입력 3

8
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 1
4 5 6 7 8 9 1 2
5 6 7 8 9 1 2 3
6 7 8 9 1 2 3 4
7 8 9 1 2 3 4 5
8 9 1 2 3 4 5 6

예제 출력 3

23

문제 해석

bfs와 combinations를 이용해서 풀려고 해봤지만 아무리 봐도 완전 탐색으로 푸는 것이랑 별반 차이가 없을 것 같아서 혹시 하는 마음에 brute force로 풀어봤는데 정답이다. 대체로 입력 값의 범위가 현저히 적고, 도저히 어떤 알고리즘도 생각이 나지 않는다면 brute force로 시도해 보는 것이 좋다.

풀이

• 우리는 d1 d2 x y에 대해서 입력을 받은 것이 없다. 우리가 알고 있는 것은 이들의 범위이다.
• 그렇다면 범위를 이용하여 나오는 경우의 수를 생각을 하여야 하는데, 각 변수들이 서로 영향을 미치고 있기 때문에 조합을 사용할 수가 없다.
• 그래서 이 4개의 변수들을 각 범위에 맞게 루프를 돌면서 모든 경우의 수를 생각하는 것이다.
• 일단 여기서 좌표는 0번지를 포함하지 않는다.
• 그렇기 때문에 graph에서 0번지를 포함하는 것들을 전부 0으로 초기화를 시켜주고 그것들을 제외한 나머지에 입력을 받는다.
• 방문을 했는지 체크하기 위한 visit 리스트도 똑같이 초기화를 해준다.
• 문제에서 나왔듯이

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

• 이런식의 범위를 요청받았다.
• 다른 변수들에게 영향을 안받는 변수인 d1과 d2를 이중 루프로 먼저 돌려준다.
• 그 후, x와 y는 d1과 d2에게 영향을 받으니 그다음 이중 루프를 x와 y로 잡아준다.
• 각 범위에 맞게끔 루프를 잡아주고 5번 선거구부터 생각을 한다.

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)

• 1번부터 4번까지 각자 다 방문했는지 체크하면서 방문을 했으면 1로 만들어주고 그래프 안의 인구수를 sum_list[4]에 더해준다.
• 여기서 주의해야할 점은 4개의 범위들이 경계선이라는 것이다.
• 경계선 안에 있는 수들은 체크를 하지 않기 때문에 경계선을 먼저 방문하고 나서 그 안의 인구수들까지 체크를 하면서 더해줘야한다.
• 이렇게 경계선을 그리고 나면 경계선 안의 인구수들을 찾아야한다.
• 예를 들어보자

0 0 0 0 0 0
0 0 1 0 0 0
0 1 0 1 0 0
1 0 0 0 1 0
0 1 0 1 0 0
0 0 1 0 0 0

• 위에 처럼 경계선이 그려진다면 우리는 다시 루프를 첫 행부터 돌아야 한다.
• 여기서 주목해야 할 점은 경계선 안에 있는 숫자들이 존재하는 행에는 1이 두 개 존재하고, 나머지 행에는 1이 한개밖에 존재하지 않는다.
• 첫 출발 행이 1이 한개고, 끝 행이 1이 한개이다.
• 그래서 graph[i].count(1) == 1이면 flag += 1로 해준다.
• 물론 flag의 첫 값은 0이다.
• 그리고 끝 행에 가게 된다면 flag 값은 2가 된다. 그렇다면 루프를 빠져나오게 해준다.
• 만약 graph[i].count(1) == 2 이면 다시 루프를 돌면서 처음 1이 어디서 시작이 되는지 본다.
• 여기서도 flag를 이용하여 처음 1이 발견되었을때 위에처럼 + 1을 해준다. 물론 위에서 사용하였던 flag 변수랑은 이름을 다르게 해야 한다.
• 다음 1이 나오기 전까지 graph 값들을 전부 sum_list[4]에 더해준다.
• 그리고 마지막 1이 나오게 되면 flag 값을 + 1 더 해주었으니 2가 되어서 루프를 빠져나오게 해준다.
• 이렇게 경계선과 경계선 안에 있는 인구수까지 다 더해서 5번 선거구의 인구수를 다 더하였다.
• 그렇다면 이제 문제에서 주어진 1, 2, 3, 4번 선걱구들의 범위를 이용하여 graph 값들을 다 더해준다.

    - 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

• 여기서도 주의해야 할 점이 각 선거구들과 5번 선거구의 범위가 겹치는 곳이 존재한다.
• 하지만 이미 위에서 5번 선거구들이 방문한 곳을 1로 만들어 줬기 때문에 범위 안에 존재하면서, 방문하지 않은 곳만 각 선거구 번호에 맞게 인구수를 더해주면 된다.
• 그렇게 쭉 돌고나면 수많은 d1, d2, x, y의 경우 중 1가지가 1번부터 5번 선거구까지 인구수들을 sum_list에 넣어주게 된다.
• 여기서 max값과 min값을 구해서 차를 구한 후 min_list에 넣어준다.
• 그리고 visit 리스트와 sum_list들을 초기화 시켜주고 모든 경우의 수를 위의 과정과 같이 반복해주면 된다.

import sys

N = int(sys.stdin.readline())

graph = [[0] for _ in range(N + 1)]
visit = [[0] * (N + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    graph[i] = [0] + list(map(int, sys.stdin.readline().split()))

sum_list = [0] * 5
min_list = []

for d1 in range(1, N):
    for d2 in range(1, N):
        for x in range(1, N - d1 - d2 + 1):
            for y in range(1 + d1, N - d2 + 1):
                for i in range(d1 + 1):
                    if visit[x + i][y - i] == 0:
                        sum_list[4] += graph[x + i][y - i]
                        visit[x + i][y - i] = 1
                    if visit[x + d2 + i][y + d2 - i] == 0:
                        sum_list[4] += graph[x + d2 + i][y + d2 - i]
                        visit[x + d2 + i][y + d2 - i] = 1
                for j in range(d2 + 1):
                    if visit[x + j][y + j] == 0:
                        sum_list[4] += graph[x + j][y + j]
                        visit[x + j][y + j] = 1
                    if visit[x + d1 + j][y - d1 + j] == 0:
                        sum_list[4] += graph[x + d1 + j][y - d1 + j]
                        visit[x + d1 + j][y - d1 + j] = 1
                flag_i = 0
                for i in range(N + 1):
                    flag_j = 0
                    if visit[i].count(1) == 2:
                        for j in range(N + 1):
                            if visit[i][j] == 1:
                                flag_j += 1
                            elif flag_j == 1:
                                sum_list[4] += graph[i][j]
                                visit[i][j] = 1
                            elif flag_j == 2:
                                break
                    elif visit[i].count(1) == 1:
                        flag_i += 1
                        if flag_i == 2:
                            break
                for i in range(1, N + 1):
                    for j in range(1, N + 1):
                        if visit[i][j] == 0:
                            if 1 <= i < x + d1 and 1 <= j <= y:
                                sum_list[0] += graph[i][j]
                                visit[i][j] = 1
                            elif 1 <= i <= x + d2 and y < j <= N:
                                sum_list[1] += graph[i][j]
                                visit[i][j] = 1
                            elif x + d1 <= i <= N and 1 <= j < y - d1 + d2:
                                sum_list[2] += graph[i][j]
                                visit[i][j] = 1
                            else:
                                sum_list[3] += graph[i][j]
                                visit[i][j] = 1
                min_list.append(max(sum_list) - min(sum_list))
                sum_list = [0] * 5
                visit = [[0] * (N + 1) for _ in range(N + 1)]
print(min(min_list))  

고찰

• 생각해야할 범위가 너무나도 많아서 머리가 너무 아팠다.
• 브루트 포스 문제들은 대체로 범위 지정과 예외 처리가 핵심이다.
• 코딩을 하기 전 모든 예외들을 전부 생각해 놓고 시작하는 것이 시간을 줄일 수 있는 유일한 방법이다.