게리맨더링 2 [백준 17779번]

문제

 

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

17779번: 게리맨더링 2

 

내 풀이

 

문제 풀기 전에 인구수가 적힌 그리드의 인덱스가 1부터 시작한다는 점을 생각하고 가야 한다.

 

가장 고민을 많이 한 것은 '경계 안에 어떻게 5로 채울지'였다.

i번 행을 확인하면서 5가 2개 들어있는 행만 5의 위치를 알아내었다.

5가 i번 행의 a열과 i번 행의 b열에 있다면, i번 행의 a+1열에서 b열까지를 모두 5로 만들어주었다.

 

N = int(input())
# 1부터 시작하는 그리드
grid = [[0] + list(map(int, input().strip().split())) for _ in range(N)]
grid = [[0]*N] + grid

def board(x, y, d1, d2):
    sector = [[0]*(N+1) for _ in range(N+1)]
    num = [0]*(6)
    # 1
    dx, dy = [i for i in range(d1+1)], [j for j in range(d1+1)]
    for i in range(len(dx)):
        nx, ny = x+dx[i], y-dy[i]
        if not sector[nx][ny]:
            sector[nx][ny] = 5
            num[5] += grid[nx][ny]
    # 2
    dx, dy = [i for i in range(d2+1)], [j for j in range(d2+1)]
    for i in range(len(dx)):
        nx, ny = x+dx[i], y+dy[i]
        if not sector[nx][ny]:
            sector[nx][ny] = 5
            num[5] += grid[nx][ny]
    # 3
    dx, dy = [i for i in range(d1, d1+d2+1)], [j for j in range(d1, d1-d2-1, -1)]
    for i in range(len(dx)):
        nx, ny = x+dx[i], y-dy[i]
        if not sector[nx][ny]:
            sector[nx][ny] = 5
            num[5] += grid[nx][ny]
    # 4
    dx, dy = [i for i in range(d2, d2+d1+1)], [j for j in range(d2, d2-d1-1, -1)]
    for i in range(len(dx)):
        nx, ny = x+dx[i], y+dy[i]
        if not sector[nx][ny]:
            sector[nx][ny] = 5
            num[5] += grid[nx][ny]

    # 경계안에 5로 채우기
    for i in range(1, N+1):
        five = []
        if sector[i].count(5) == 2:
            for j in range(1, N+1):
                if sector[i][j] == 5:
                    five.append(j)
            for j in range(five[0]+1, five[1]):
                sector[i][j] = 5
                num[5] += grid[i][j]

    # 1, 2, 3, 4 채우기
    for r in range(1, N+1):
        for c in range(1, N+1):
            if 1 <= r < x+d1 and 1 <= c <= y and not sector[r][c]:
                sector[r][c] = 1
                num[1] += grid[r][c]
            elif 1 <= r <= x+d2 and y < c <= N and not sector[r][c]:
                sector[r][c] = 2
                num[2] += grid[r][c]
            elif x+d1 <= r <= N and 1 <= c < y-d1+d2 and not sector[r][c]:
                sector[r][c] = 3
                num[3] += grid[r][c]
            elif x+d2 < r <= N and y-d1+d2 <= c <= N and not sector[r][c]:
                sector[r][c] = 4
                num[4] += grid[r][c]

    return max(num[1:]) - min(num[1:])
# d1, d2 최대값 N-1
MIN = 1e9
for d1 in range(1, N):
    for d2 in range(1, N):
        for x in range(1, N+1):
            for y in range(1, N+1):
                if x+d1+d2 <= N and 1 <= y-d1 <y and y+d2 <= N:
                    res = board(x, y, d1, d2)
                    MIN = min(MIN, res)
print(MIN)

 

총평

구현구현!