[삼성SW역량][Python/BOJ] 백준 17779 게리맨더링2(구현)

 

 

처음 문제를 봤을 때 조건이 너무 많아서 어질했다. 

어떤 방법을 써야할지 모르겠어서 답을 봤더니 정말 그 많은 조건들을 다 구현하면 되는 문제였다. 

두려워하지말고 하나하나 구현해야겠다는 생각을 했다. 

 

 

 

 

 

1. 4중 for문을 돌면서 조건에 맞는 x, y, d1, d2를 선택하여 cal 함수를 돌린다.

 

2. cal 함수 

   2-1. 경계면을 5번으로 할당

   2-2. 경계면 내부를 5번으로 할당

   2-3. 전체 구역을 돌면서 1,2,3,4,5의 인구를 구한다.

   2-4. 각 인구의 최대값, 최소값을 구해 뺀 수를 반환한다. 

 

 

 

 

 

경계면 내부를 5로 만들 때 행을 x+1 부터 x+d1+d2까지 돌린다는 것을 잊지말아야한다. 

경계면 가장 위의 행이 x이고 가장 아래 행은 x+d1+d2이기 때문이다.

경계면 내부를 5로 만들기 위해서는 이들 사이를 지나야한다. x행에는 5가 한개 뿐이므로  지나갈 이유가 없고

x+d1+d2도 5가 1개이고 내부에 5로 만들 위치가 없다. 그러므로 

for i in range(x+1, x+d1+d2) : 로 해야한다. 

 

---

 

 

 

def cal(x,y,d1,d2) :
    elec = [0 for i in range(5)] # 선거구 당 인구수 
    temp = [[0]*(n+1) for i in range(n+1)] # 선거구 
    
    # 경계선을 5번 선거구로 할당 
    for i in range(d1+1) :
        temp[x+i][y-i] = 5 # 1번 조건 
        temp[x+d2+i][y+d2-i] = 5 # 4번 조건 
    for i in range(d2+1) :
        temp[x+i][y+i] = 5 # 2번 조건 
        temp[x+d1+i][y-d1+i] =5 # 3번 조건 
        
        
    # 경계선 내부를 5번으로 할당 
    for i in range(x+1, x+d1+d2) : # 행을 돌면서 
        flag = False 
        for j in range(1,n+1) : # 열을 돌면서 
            if temp[i][j] == 5 : # 경계선 발견! 
                flag = not flag 
            if flag :
                temp[i][j] = 5 
    
    # 전체 구역을 돌면서 1,2,3,4 부여 
    for r in range(1,n+1) :
        for c in range(1,n+1) :
            if r<x+d1 and c<=y and temp[r][c] == 0 :
                elec[0] += board[r][c] # 1번 
            elif r<=x+d2 and y<c and temp[r][c] == 0:
                elec[1] += board[r][c] #2번 
            elif x+d1<=r and c<y-d1+d2 and temp[r][c] == 0 :
                elec[2] += board[r][c] # 3번  
            elif x+d2< r and y-d1+d2<= c and temp[r][c] == 0:
                elec[3] += board[r][c] # 4번 
            elif temp[r][c] == 5:
                elec[4] += board[r][c] # 5번 
    return max(elec) - min(elec)
            
                
                
            
                    
if __name__=="__main__" :
    n = int(input())
    board = [[]]

    for _ in range(n):
        # 1-index로 맞추기위해서 
        board.append([0] + list(map(int, input().split())))
    
    answer = int(1e9)
    for x in range(1,n+1) :
        for y in range(1, n+1) :
            for d1 in range(1,n+1) :
                for d2 in range(1,n+1) :
                    if 1<=x<x +d1 +d2 <=n and 1<=y-d1<y<y+d2<=n :
                        answer = min(answer ,cal(x,y,d1,d2))
    print(answer)

 

 

 

참고 블로그 : 

https://yeon-code.tistory.com/m/89

[python] BOJ 백준 17779: 게리멘더링2