[백준] 17779 게리맨더링2 - Python - 구현

https://www.acmicpc.net/problem/17779

17779번: 게리맨더링 2

어렵다고 생각한 구현문제이다 삼성 기출문제이다 

풀이방법
1 .경계선 표시하기 : 경계선에 5 라고 저장하기 

2. 구역 1, 구역2, 구역 3, 구역 4의 각각 구역마다의 총인원수를 구해준 후에 구역 5는 (전체 인구수) - (구역1+구역2+구역3+구역4)

3. max값과 min값의 차이가 최소값이 되는 경우로 갱신해주기 

인데 구현을 디테일하게 해주어야 한다.. 

1) 예시는 맞았으나 히든케이스에서 틀린 풀이

반례 
이 경우 답은 158이 나와야 한다. 

14
65 1 33 1 1 1 14 1 1 1 1 1 100 1
1 32 1 43 1 71 1 1 1 1 41 1 1 1
1 1 75 1 81 17 1 1 15 1 1 31 1 12
1 1 100 1 1 1 13 1 1 1 13 1 1 1
20 1 1 1 1 1 1 1 99 1 1 1 1 1
1 1 1 1 1 1 1 79 1 14 1 1 1 1
1 30 1 1 1 1 1 1 1 1 10 1 1 1
1 34 1 1 1 77 1 1 1 1 10 1 1 1
1 1 1 100 1 1 1 51 21 100 1 10 1 1
8 1 1 1 88 1 1 1 13 1 1 1 1 1
1 1 100 1 1 1 31 1 1 1 1 100 1 1
1 9 1 1 100 1 1 1 1 1 100 1 1 1
1 2 1 1 1 1 100 1 1 1 1 1 1 1
3 100 55 1 1 1 100 100 1 1 1 1 1 1

2) 정답코드 

여기서 놓쳤던 부분은, 2번구역과 4번구역의 경우 y값 큰것부터 작은것으로 감소시켜나가야 구역 5번을 만난다는 것이다 

n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

answer = int(1e9)  # 기준점, 경계의 길이 정하기
total = 0
for i in range(n):
    total += sum(graph[i])

def simulate(x, y, d1, d2):
    t1, t2, t3, t4 = 0, 0, 0, 0
    check = [[0] * n for _ in range(n)]  # 경계선을 기록
    # 5번 선거구 경계선 표시하기
    # (x, y), (x+1, y-1), ..., (x+d1, y-d1)
    for i in range(d1 + 1):
        check[x+i-1][y-i-1] = 5
    # (x, y), (x+1, y+1), ..., (x+d2, y+d2)
    for i in range(d2+1):
        check[x+i-1][y+i-1] = 5
    # (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
    for i in range(d2+1):
        check[x+d1+i-1][y-d1+i-1] = 5
    # (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
    for i in range(d1+1):
        check[x+d2+i-1][y+d2-i-1] = 5

    # 경계선 만나면 break (check 칸 값이 5이면 중단)
    # 구역 1
    for i in range(1, x+d1):
        for j in range(1, y+1):
            if check[i-1][j-1] == 5:
                break
            t1 += graph[i-1][j-1]

    for i in range(1, x+d2+1):
        for j in range(n, y, -1):
            if check[i-1][j-1] == 5:
                break
            t2 += graph[i-1][j-1]

    for i in range(x+d1, n+1):
        for j in range(1, y-d1+d2):
            if check[i-1][j-1] == 5:
                break
            t3 += graph[i-1][j-1]

    for i in range(x+d2+1, n+1):
        for j in range(n, y-d1+d2-1, -1):
            if check[i-1][j-1] == 5:
                break
            t4 += graph[i-1][j-1]

    t5 = total - (t1+t2+t3+t4)
    max_t = max(t1,t2,t3,t4,t5)
    min_t = min(t1,t2,t3,t4,t5)
    return max_t-min_t

#가능한 x, y, d1, d2의 경우의 수
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, n-d2+1):
                # 최솟값 갱신
                answer = min(simulate(x, y, d1, d2), answer)

print(answer)