백준 #17779 - [G3] 게리맨더링 2 : 구현, 브루트포스

(python3)

17779번: 게리맨더링 2

 

 

케이스 분리

특별한 알고리즘은 없었고, 모든 경우의 수를 케이스 분리해서 해결했습니다. 구현에만 집중해서 중첩이 너무 많습니다. 그닥 매력적인 풀이는 아닌 것 같네요..

d1, d2, x, y 의 조건을 문제에서 줬기 때문에 거기에 맞춰서 작성했고, 문제에서는 x,y 를 1부터 시작하는 인덱스로 제시해서 그 부분만 0부터 시작하는 인덱스로 바꿔서 적용해줬습니다.

 

코드

def solution(input) : 
	# 입력 받기
    N = int(input().strip())
    PMAP = []
    for _ in range(N) :
        PMAP.append(list(map(int,input().split())))
    
    min_cal = [] # 최소값 저장
    for d1 in range(1,N) :
        for d2 in range(1,N) :
            for r in range(N) :
                for c in range(N) : # d1,d2,r,c의 모든 경우의 수 탐색
                    if r+d1+d2 <= N-1 and 0<=c-d1 and c+d2<=N-1 : # 경계가 조건에 부합하는지
                        g1,g2,g3,g4,g5 = 0,0,0,0,0 # 각 구역별 인구수 저장
                        for rr in range(N) :
                        	# 행들의 케이스 분리. pl, pr 은 경계 인덱스.
                            if rr < r : # 기준점보다 위쪽
                                pl = pr = -1
                            elif rr > r+d1+d2 : # 기준점보다 아래쪽
                                pl = pr = -2
                            elif rr == r : # 기준점
                                pl = pr = c
                                flag1 = 1
                                flag2 = 2
                            elif rr == r+d1+d2 : # 아래쪽 꼭지점
                                pl = pr = c-d1+d2
                                flag1 = 3
                                flag2 = 4
                            else : # 사이에 낀거
                                if rr <= r+d1 :
                                    pl -= 1
                                    flag1 = 1 # pl 왼쪽 구역이 몇번 구역인지 표시
                                    if rr == r+d1 : flag1 = 3
                                else :
                                    pl += 1
                                    flag1 = 3
                                if rr <= r+d2 :
                                    pr += 1
                                    flag2 = 2 # pr 오른쪽 구역이 몇번 구역인지 표시
                                else :
                                    pr -= 1
                                    flag2 = 4

                            for cc in range(N) :
                                p = PMAP[rr][cc]
                                if pl == -1 : # 기준보다 위쪽이면
                                    if cc <= c : # 왼쪽은 1번구역
                                        g1+=p
                                        gmap[rr][cc] = 1
                                        continue
                                    else : # 오른쪽은 2번 구역
                                        g2+=p
                                        gmap[rr][cc] = 2
                                        continue
                                elif pl == -2 : # 아래 꼭짓점보다 아래쪽이면
                                    if cc < c-d1+d2 : # 왼쪽은 3번 구역
                                        g3+=p
                                        gmap[rr][cc] = 3
                                        continue
                                    else : # 오른쪽은 4번 구역
                                        g4+=p
                                        gmap[rr][cc] = 4
                                        continue
                                else : # 경계면 안쪽이면
                                    if cc < pl : # 경계 왼쪽
                                        if flag1 == 1 :
                                            g1+=p
                                            gmap[rr][cc] = 1
                                        elif flag1 == 3 :
                                            g3+=p
                                            gmap[rr][cc] = 3
                                        continue
                                    elif pl <= cc and cc <= pr : # 경계 안쪽
                                        g5 += p
                                        gmap[rr][cc] = 5
                                        continue
                                    else : # 경계 오른쪽
                                        if flag2 == 2 :
                                            g2+=p
                                            gmap[rr][cc] = 2
                                        elif flag2 == 4 : 
                                            g4+=p
                                            gmap[rr][cc] = 4
                        # 최소, 최대 인구의 차 구하고, 차들의 최솟값 갱신하기
                        min_g = min([g1,g2,g3,g4,g5])
                        max_g = max([g1,g2,g3,g4,g5])
                        min_cal.append(max_g - min_g)
                        min_cal = [min(min_cal)]    
        
    print(min_cal[0])
solution(input)

 

my solved.ac :

solved.ac