알고리즘 풀이 백준(BOI) 17779) 게리맨더링 2 (Python)

백준(BOI) 17779 - 게리맨더링 2

---

 

 

17779번: 게리맨더링 2

 

[문제풀이]

 

 

 선거구를 5개로 분할하여  각 선거구에 있는 사람들을 합하였을 때 가장 많은 사람이 있는 선거구와 가장 적은 사람이 있는 선거구의

 

 최소값을 구하는 문제이다. 선거구는 문제에 주어져 있는 공식대로 분할되며 시작점을 어디로 하는 지에 따라 여러가지 경우의 수가 

 

 나올 수 있다. 필자는 브루트포스로 모든 경우의 수를 계산하여 각 경우의 수 마다 최소값을 갱신하는 방식으로 풀었다.  

 

 선거구의 경계를 나누는 방식에서 1 ~ 4 번 선거구 먼저 할당해주고 5번 선거구의 경계선을 그려주고 경계선 안의 구역을 5번으로 

 

 채우는 방식으로 풀었다. 문제를 풀다가 5번 선거구 경계선 안쪽을 5번 선거구로 채우는 과정에서 실수를 한 번 했었는데, 

 

 다음과 같은 경우는 탐색을 이용해서 5번 선거구를 채울 수 없으므로 반복문 조건을 잘 짜주어서 채우는 방식으로 해결하였다.

 

 0  5  0  0
 5      5  0
 0  5      5
 0  0  5  0

 위와 같은 경우에서는 탐색을 이용하여 경계선 안쪽을 매꿀 수가 없었다.

 (빈 칸을 0으로 그려놨지만 알고리즘에서 1 ~ 4번 선거구 먼저 채워주었으므로 더욱 그렇다)

 

 

 문제에서 주어진 로직은 다음과 같다.

 1. 기준점 (row, col)과 경계선의 길이(d1, d2)를 정한다.
 2. 주어진 공식대로 경계선을 그린다.
 3. 경계선과 경계선 안의 구역을 5번 선거구로 채운다.
 4. 경계선 밖의 구역은 주어진 공식대로 1, 2, 3, 4번 선거구로 채운다.
 5. 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구한다.

 주어진 로직대로라면 5번 선거구 먼저 채우고 1~4번 선거구를 확정지어야 하지만 필자는 1~4번 선거구 먼저 채웠다.

 

 문제의 공식은 row, col 값이 0이 아닌 1부터 시작하므로 이것만 주의해서 공식을 작성하면 쉽게 통과 될 수 있을 것이다.

 

 브루트포스로 풀은데다가 별다른 종료조건을 주지 않아 메모리와 시간초과가 걱정되었지만 무난히 통과하였다

 

 

---

 

[전체 소스코드]

def calc(sepgrid):
    global n, objgrid,minresult
    maxnum = -987654321
    minnum = 987654321
    result = [0 for _ in range(5)]
    for i in range(n):
        for j in range(n):
            if sepgrid[i][j] == 1 : result[0] += objgrid[i][j]
            elif sepgrid[i][j] == 2 : result[1] += objgrid[i][j]
            elif sepgrid[i][j] == 3 : result[2] += objgrid[i][j]
            elif sepgrid[i][j] == 4 : result[3] += objgrid[i][j]
            elif sepgrid[i][j] == 5 : result[4] += objgrid[i][j]
    for num in result:
        maxnum = max(num,maxnum)
        minnum = min(num,minnum)
    minresult = min(maxnum-minnum, minresult)
    
    
def separate(row,col,d1,d2):
    global n
    sepgrid = [[0 for _ in range(n)] for _ in range(n)]
    
  
    #sep1
    for i in range(row+d1):
        for j in range(col+1):
            sepgrid[i][j] = 1
    #sep2 
    for i in range(row+d2+1):
        for j in range(col+1,n):
            sepgrid[i][j] = 2
    
    #sep3 
    for i in range(row+d1, n):
        for j in range(col-d1+d2):
            sepgrid[i][j] = 3
    
    #sep4
    for i in range(row+d2+1,n):
        for j in range(col-d1+d2,n):
            sepgrid[i][j] = 4

    #sep5
    temp = col
    for i in range(row, row+d1+1):
        sepgrid[i][temp] = 5
        temp -= 1
    temp = col
    for i in range(row, row+d2+1):
        sepgrid[i][temp] = 5
        temp += 1
    temp = col-d1
    for i in range(row+d1, row+d1+d2+1):
        sepgrid[i][temp] = 5
        temp += 1
    temp = col+d2
    for i in range(row+d2, row+d2+d1+1):
        sepgrid[i][temp] = 5
        temp -= 1
    for i in range(row+1,row+d1+d2):
        oper = False
        for j in range(0, n):
            if sepgrid[i][j] == 5 and not oper : 
                oper = True 
                continue
            if oper and sepgrid[i][j] == 5 : oper = False
            if oper : sepgrid[i][j] = 5

    calc(sepgrid)

def go(row, col):
    global n
    for d1 in range(1,n-1):
        for d2 in range(1,n-1):
            if 1 <= (row+1) < (row+1)+d1+d2 <= n and 1 <= (col+1)-d1 < (col+1) < (col+1) + d2 <= n:
                separate(row,col,d1,d2) 

n = int(input())
objgrid = [list(map(int,input().split())) for _ in range(n)]
minresult = 987654321
for i in range(n-2):
    for j in range(1,n-1):
        go(i,j)

print(minresult)