[BOJ] 17779. 게리맨더링2 (🥇, 구현/시뮬레이션)

문제

풀이

구역별 인구수 구하기

5구역과 맞닿는 부분은 for문을 사용해서 열을 한칸씩 줄여가면서(혹은 늘려가면서) 구했고, 그 외의 위(또는 아래) 부분은 그냥 경계선이 되는 열까지 행별로 구해서 바로바로 더해줬다

def findOne(x, y, d1):
    one = 0
    for row in arr[:x]:
        one += sum(row[:y+1])
    
    for i in range(d1):
        one += sum(arr[x+i][:y-i])
    
    return one

for row in arr[:x] 는 5구역의 시작이 되는 x행 이전까지의 행까지만 구하겠다는 뜻이고, sum(row[:y+1])는 그 행들 중에서도 1구역이 가질 수 있는 경계가 되는 y열까지의 값만 더하겠다는 뜻이다.

5구역과 맞닿는 부분은 5구역이 한 칸씩아래로 내려갈수록 한 칸씩 열이 줄어든다는 점을 이용했고, 1구역의 경우 5구역과 맞닿는 행이 d1 만큼이기 때문에 for i in range(d1)으로 반복문을 구성했다. 행이 한 칸씩 내려갈때마다(x+i) 한 칸씩 줄어든 열을 더하겠다([:y-i])는 방식

잘못된 풀이1

(0, 1) 부터 시작해서 (N-2, N-1)의 칸 까지 d1, d2를 각각 뻗어나갈 수 있게 하는 재귀 방식으로 짜려고 했지만 이렇게 하는 경우 이미 방문했던 칸에서 이미 계산했던 구역을 여러번 또 계산하게 되는 불필요한 중복 계산이 계속 발생하게 됨

# 게리맨더링 2

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
total = sum([sum(row) for row in arr])
ans = 1e9

def _init():
    ward = [0]*5
    ward[0] = arr[0][0]
    ward[1] = sum(arr[0][2:]+arr[1][3:]+arr[2][2:])
    ward[2] = arr[2][0]

    for row in arr[3:]:
        ward[2] += sum(row[:1])
        ward[3] += sum(row[1:])

    ward[4] = total - sum(ward[:4])

    return ward

ward = _init()

def gerry(ward, x, y, d1, d2):
    global ans
    ans = min(ans, max(ward)-min(ward))

    if x+3<N: # 더 아래 행으로 내려갈 수 있으면
        row_ward = ward[:]
        gerry(row_ward, x+1, y, d1, d2)
    
    if y+2<N: # 더 옆의 열로 이동할 수 있으면
        col_ward = ward[:]
        gerry(col_ward, x, y+1, d1, d2)
    
    if 0<y-d1 and x+d1+d2<N-1:
        d1_ward = ward[:]
        gerry(d1_ward, x, y, d1+1, d2)

    if y+d2<N-1 and x+d1+d2<N-1:
        d2_ward = ward[:]
        gerry(d2_ward, x, y, d1, d2+1)

#### gerry(ward, 0, 1, 1, 1)

잘못된 풀이2

• d1, d2는 최소 1의 값을 가지기 때문에 최소한의 이 범위를 맞추기 위해서는 x(행)은 0~N-2, y(열)은 1~N-1 범위 내에 있어야 한다

• 그래서 이 범위 내에서 d1, d2를 늘렸을 때 가능한 범위인지를 확인하고 늘리는 expand 함수를 작성했다.

• d1을 1 늘리려면 왼쪽 아래가 증가하기 때문에 주황색과 초록색 부분의 범위가 영역을 벗어나지 않는지 확인해야 한다. 주황색의 행 부분 x+d1+d2와 초록색의 열 부분 y-d1 의 값에서 d1이 1씩 증가해도 배열 범위 내에 들어오는지 확인한 후에 가능하다면 d1을 재귀로 1 늘리는 방식이다
• d2도 마찬가지다. 오른쪽 아래가 증가하기 때문에 파란색의 열 y+d2와 주황색의 행 x+d1+d2를 확인하면 된다.

import sys
input = sys.stdin.readline

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
total = sum([sum(row) for row in arr])
ans = 1e9

def findOne(x, y, d1):
    one = 0
    for row in arr[:x]:
        one += sum(row[:y+1])
    
    for i in range(d1):
        one += sum(arr[x+i][:y-i])
    
    return one

def findTwo(x, y, d2):
    two = 0
    for row in arr[:x+1]:
        two += sum(row[y+1:])
    
    for i in range(1, d2+1):
        two += sum(arr[x+i][y+i+1:])

    return two

def findThree(x, y, d1, d2):
    three = 0
    for i in range(d2+1):
        three += sum(arr[x+d1+i][:y-d1+i])

    for row in arr[x+d1+d2+1:]:
        three += sum(row[:y-d1+d2])

    return three

def findFour(x, y, d1, d2):
    four = 0

    for i in range(1, d1+1):
        four += sum(arr[x+d2+i][y+d2-i+1:])

    for row in arr[x+d1+d2+1:]:
        four += sum(row[y-d1+d2:])
    
    return four

def Ward(x, y, d1, d2):
    ward = [findOne(x, y, d1), findTwo(x, y, d2), findThree(x, y, d1, d2), findFour(x, y, d1, d2)]
    ward.append(total-sum(ward))
    ward.sort()
    # print(x, y, d1, d2, ward)
    return ward[-1]-ward[0]

def expand(x, y, d1, d2):
    global ans
    if ans < (t:=Ward(x, y, d1, d2)):
        ans = t

    if x+d1+d2+1<N and y-d1>0:
        expand(x, y, d1+1, d2)
        
    if x+d1+d2+1<N and y+d2+1<N:
        expand(x, y, d1, d2+1)

for x in range(N-2):
    for y in range(1, N-1):
        expand(x, y, 1, 1)

print(ans)

근데 결과는 ㅋㅎ

시간초과였다.
테케나 반례는 전부 통과가 되고, 배열의 크기도 20x20이라 진짜 최대로 완탐해도 20x20x400 = 160000 이라고 생각했는데 어떻게 고쳐도 시간초과였다ㅜ
다른 블로그 해설이나 풀이를 보면 완탐으로 해도 초과가 안 난다고 하는데 나는 왜 자꾸 나는지 모를일이었다. 대다수의 블로그 풀이랑 내 풀이의 가장 큰 차이는

1. 5구역의 경계를 치고 인구수를 구하느냐 아니냐
2. d1, d2가 뻗어나가는 게 재귀냐 반복문이냐

였는데 아무리봐도 1번은 문제가 아닌 것 같았다. 그랬다면 애초에 테케에서 틀렸어야 맞았다. 그렇다면 2번이 문제인건데... 정확한 이유는 모르겠지만 2번에서 d1, d2가 뻗어나갈 때 불필요한 중복이 계속 발생하는 거 같았다. 그래서 재귀를 포기하고 일단 반복문으로 바꿔줬다

# 232ms

import sys
input = sys.stdin.readline

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
total = sum([sum(row) for row in arr])
ans = 1e9

# 1구역 구하기
def findOne(x, y, d1):
    one = 0
    for row in arr[:x]:
        one += sum(row[:y+1])
    
    for i in range(d1):
        one += sum(arr[x+i][:y-i])
    
    return one

# 2구역 구하기
def findTwo(x, y, d2):
    two = 0
    for row in arr[:x+1]:
        two += sum(row[y+1:])
    
    for i in range(1, d2+1):
        two += sum(arr[x+i][y+i+1:])

    return two

# 3구역 구하기
def findThree(x, y, d1, d2):
    three = 0
    for i in range(d2+1):
        three += sum(arr[x+d1+i][:y-d1+i])

    for row in arr[x+d1+d2+1:]:
        three += sum(row[:y-d1+d2])

    return three

# 4구역 구하기
def findFour(x, y, d1, d2):
    four = 0

    for i in range(1, d1+1):
        four += sum(arr[x+d2+i][y+d2-i+1:])

    for row in arr[x+d1+d2+1:]:
        four += sum(row[y-d1+d2:])
    
    return four

# 1~5구역 인구수 구해서 리스트로 만들고 최대 - 최소 값 반환하기
def Ward(x, y, d1, d2):
    ward = [findOne(x, y, d1), findTwo(x, y, d2), findThree(x, y, d1, d2), findFour(x, y, d1, d2)]
    ward.append(total-sum(ward))
    # print(x, y, d1, d2, ward)
    return max(ward)-min(ward)

# 변경된 부분
for x in range(N-2):
    for y in range(1, N-1):
        for d1 in range(1, N):
            for d2 in range(1, N):
                if x+d1+d2>=N or y-d1<0 or y+d2>=N:
                    continue
                print(x, y, d1, d2)
                t = Ward(x, y, d1, d2)
                if ans > t:
                    ans = t

print(ans)

232ms로 깔끔하게 통과했지만 여전히 왜 저 방식은 안 되고 이 방식은 되는지가 문제였다

불필요한 중복이 발생하긴 하나?

우선, 중복이 발생하긴 하는지부터 확인해봤다

1. 재귀로 짠 코드와 2. 반복문으로 짠 코드 가 어떤 x, y, d1, d2 값을 방문하는지 확인 후 출력하고 각각 A와 B 에 저장했다.(중복x)
A는 중복이 없는 set()이고 _A는 중복 가능한 list이다

A = set()
_A = []
while True:
    t = input()
    if t == '0':
        break
    A.add(t)
    _A.append(t)

B = set()
while True:
    t = input()
    if t == '0':
        break
    B.add(t)

print(A-B)
print(len(A), len(_A))

결과는 중복으로 방문한 부분이 아주 많았습니다 대략 122번 그러니까 1/3 정도 중복으로 들어감. 그래서 시간초과가 나는거였다

그럼 왜? 어디서 발생하는거지??

x, y = 0, 4 일 때의 경우다

우선 내가 생각한 코드의 진행방식은 이렇다
범위를 확인하고 d1을 늘릴 수 있으면 늘린다.
늘릴 수 없는 범위라면 재귀이기 때문에 이전 상태로 되돌아온다.

def expand(x, y, d1, d2):
    global ans
    if ans < (t:=Ward(x, y, d1, d2)):
        ans = t
        
    # d1 늘리기
    if x+d1+d2+1<N and y-d1>0:
        expand(x, y, d1+1, d2)
        
    # d2 늘리기
    if x+d1+d2+1<N and y+d2+1<N:
        expand(x, y, d1, d2+1)

d1, d2 = 4, 1인 상태(왼쪽)에서 시작하게 된다. d1로는 더 늘어날 수 없기 때문에 if 문을 지나서 d2 늘리기를 할 수 있는지 확인하게 된다. d2로는 늘어날 수 있기 때문에 d1, d2 = 4, 2 상태가 된다(오른쪽).

더 늘어날 수 있는 곳이 없으면 함수는 종료된다. 재귀함수이기 때문에 현재 함수가 종료되면 이전의 상태로 되돌아오게 된다. 이제 다시 상태는 d1, d2 = 4, 1이 되고, 여기서도 더 늘어날 곳이 없으므로 또 함수는 종료되고 이보다 더 이전 상태로 되돌아가게 된다. 아마 d1, d2 = 3, 1이 될 것이다(d1을 계속 늘려가면서 왔을 것이므로)

d1, d2 = 3, 1(왼쪽) 상태에서 이제 d1을 늘리는 작업은 끝났으니 다음 if 문인 d2 늘리기에 들어가게 된다. d2를 늘릴 수 있으므로 d1, d2 = 3, 2가 된다(가운데).

그리고 이제 여기서 중복문제가 발생하게 된다

d1, d2 = 3, 2는 새로운 함수로 들어간 상태다. 즉 d1을 늘릴 수 있는지 확인하고 늘리는 작업을 수행하게 된다는 뜻이다. 그리고 실제로 이 상태에서 d1은 한 칸 늘릴 수 있다. 하지만 문제는 늘렸을 때의 값인 d1, d2 = 4, 2는 이미 전에 한 번 방문한 값이라는 점이다.

결국 재귀에서 d1 늘리기와 d2 늘리기가 순서대로 반복되는 탓에 이미 이전에 d1 늘리기에서 확인했던 값이 d2 늘리기를 하는 과정에서 d2 늘리고 다시 d1을 늘리면서 다시 확인하게 되는 일들이 반복해서 생겨나면서 수많은 중복이 생겨난 것이었다.. ㅠㅠ

반복문으로 작업을 수행하게 될 경우에는 이미 한 번 나온 d1, d2 가 다시 반복될 일은 없기 때문에 이런 일이 발생하지 않아서 시간초과가 나지 않는 거였다

해결하려면 방문처리를 하는 과정이 있어서 중복으로 방문되지 않게 해주면 될 거 같았다.

최종 코드

# 232ms 

import sys
input = sys.stdin.readline

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
total = sum([sum(row) for row in arr])
ans = 1e9

# 1구역 구하기
def findOne(x, y, d1):
    one = 0
    for row in arr[:x]:
        one += sum(row[:y+1])
    
    for i in range(d1):
        one += sum(arr[x+i][:y-i])
    
    return one

# 2구역 구하기
def findTwo(x, y, d2):
    two = 0
    for row in arr[:x+1]:
        two += sum(row[y+1:])
    
    for i in range(1, d2+1):
        two += sum(arr[x+i][y+i+1:])

    return two

# 3구역 구하기
def findThree(x, y, d1, d2):
    three = 0
    for i in range(d2+1):
        three += sum(arr[x+d1+i][:y-d1+i])

    for row in arr[x+d1+d2+1:]:
        three += sum(row[:y-d1+d2])

    return three

# 4구역 구하기
def findFour(x, y, d1, d2):
    four = 0

    for i in range(1, d1+1):
        four += sum(arr[x+d2+i][y+d2-i+1:])

    for row in arr[x+d1+d2+1:]:
        four += sum(row[y-d1+d2:])
    
    return four

# 1~5구역 인구수 구해서 리스트로 만들고 최대 - 최소 값 반환하기
def Ward(x, y, d1, d2):
    ward = [findOne(x, y, d1), findTwo(x, y, d2), findThree(x, y, d1, d2), findFour(x, y, d1, d2)]
    ward.append(total-sum(ward))
    # print(x, y, d1, d2, ward)
    return max(ward)-min(ward)

for x in range(N-2):
    for y in range(1, N-1):
        for d1 in range(1, N):
            for d2 in range(1, N):
                if x+d1+d2>=N or y-d1<0 or y+d2>=N:
                    continue
                t = Ward(x, y, d1, d2)
                if ans > t:
                    ans = t

print(ans)

후기

사실 이 문제는 안 풀려서 2일 고생했고 코드를 짜고 제출했더니 시간초과가 떠서 또 하루꼬박을 고생했던 문제였다. 애초에 구역별 인구수를 구하는 것부터가 나랑 비슷하게 구한 사람이 거의 없고, 5구역 경계를 찍는다는 방식이 대다수라서 참고하기가 너무 애매했다. 중간에 포기하고 경계 찍는 방식으로 바꿔서 아예 그 코드를 베껴서 이해해볼까 생각도 했는데 아무리 생각해도 내가 짠 로직이 틀린 것 같진 않아서 틀렸다면 적어도 왜 틀렸는지는 알아야 넘어갈 수 있을 것 같았다ㅠ 진짜 꿈에도 나올 정도로 힘들었는데...!
결국 문제는 방문처리 문제였다ㅋㅋㅋ 어딘가 중복으로 방문하고 있구나...! 하는 느낌은 오는데 도저히 이유를 알 수가 없어서 힘들던 지난 2일... 원인을 파악하고 나니 좀 살 거 같다.

그리고 이 문제를 끝으로 골드12 문제 풀기 목표도 달성! 끝!