[코드트리] 종전 (python)

🔗 문제 링크

https://www.codetree.ai/frequent-problems/war-finish/description

https://www.acmicpc.net/problem/17779 (백준 - 게리맨더링 2)

👩🏻‍💻 코드

import sys

n = int(sys.stdin.readline().rstrip())
maps = [[0] * (n + 1)] + [[0] + list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
INF = 1e9
answer = INF


def calculate_rec(x, y, d1, d2):
    temp = [[0] * (n + 1) for _ in range(n + 1)]

    temp[x][y] = 5  # 라인에 걸치는 부분 5로 설정
    for i in range(1, d1 + 1):
        temp[x + i][y - i] = 5
    for i in range(1, d2 + 1):
        temp[x + i][y + i] = 5
    for i in range(1, d2 + 1):
        temp[x + d1 + i][y - d1 + i] = 5
    for i in range(1, d1 + 1):
        temp[x + d2 + i][y + d2 - i] = 5

    R = [0] * 5  # 선거구 저장
    for r in range(1, x + d1):
        for c in range(1, y + 1):
            if temp[r][c] == 5:
                break
            R[1] += maps[r][c]
    for r in range(1, x + d2 + 1):
        for c in range(n, y, -1):
            if temp[r][c] == 5:
                break
            R[2] += maps[r][c]
    for r in range(x + d1, n + 1):
        for c in range(1, y - d1 + d2):
            if temp[r][c] == 5:
                break
            R[3] += maps[r][c]
    for r in range(x + d2 + 1, n + 1):
        for c in range(n, y - d1 + d2 - 1, -1):
            if temp[r][c] == 5:
                break
            R[4] += maps[r][c]

    R[0] = total - sum(R)
    return max(R) - min(R)


total = 0
for i in range(1, n + 1):
    total += sum(maps[i])

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 x + d1 + d2 > n:
                    continue
                if y - d1 < 1:
                    continue
                if y + d2 > n:
                    continue

                answer = min(answer, calculate_rec(x, y, d1, d2))

print(answer)

📝 정리

1. 4중 for 문을 통해 (x, y, d1, d2) 선택
2. (x, y, d1, d2)를 기반으로 경계선 5로 설정
3. 이중 for 문을 통해 선거구를 나누기
   3-1. 바깥 col -> 안쪽 col 순서로 돌기
   3-2. 경계선(5)를 마주치면 break
4. (max-min)이 최소라면, answer에 대입

저번에 풀었던 문제였는데도 어려웠다.. 처음에 로직 짤 때 제대로 짜자!