[분할정복, python] 색종이 만들기 (스택과 재귀함수로 풀어보기)

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

2630번: 색종이 만들기

처음에 짠 코드

divide라는 함수에 인자 4개를 받게하여 행의 처음과 끝, 열의 처음과 끝을 컨트롤하면 된다는 아이디어까지는 접근했다.

import sys
sys.setrecursionlimit(10**6)
# 8
# 1 1 0 0 0 0 1 1
# 1 1 0 0 0 0 1 1
# 0 0 0 0 1 1 0 0
# 0 0 0 0 1 1 0 0
# 1 0 0 0 1 1 1 1
# 0 1 0 0 1 1 1 1
# 0 0 1 1 1 1 1 1
# 0 0 1 1 1 1 1 1
n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]

def divide(_n, n, _m, m):
    global ans, arr
    isFirst = True
    for i in range(_n, n):
        for j in range(_m, m):
            if isFirst:
                origin_color = arr[i][j]
                isFirst = False
            elif arr[i][j] != origin_color:
                nowColor = arr[i][j]
                if _n <= i < (n //2) and _m <= j < (m //2):
                    return divide(_n, n//2,_m, m//2,)
                elif (n// 2) <= i and 0 <= j < (m //2):
                    return divide(n//2, n, _m, m)
                elif 0 <=  i < (n //2) and (m //2) <= j:
                    return divide(_n, n, m//2, m)
                elif (n//2) <= i and (m //2) <= j:
                    return divide(n//2,n, m//2, m)
    ans.append(origin_color)

ans = []
divide(0, n, 0, n)
print(ans.count(0))
print(ans.count(1))

하지만 디버깅을 찍었을 때 n과 m이 같은 값을 돌아서 같은 크기의 색종이를 계속 정의하고 재귀하는 상태였다.

size라는 변수를 이용해서 일일히 _n과 n, _m과 m 사이의 차이가 새로운 색종이의 폭이 될 수 있도록 하여

점점 작은 색종이를 재귀할 수 있도록 코드를 고쳤다.

또한 다른 값이 있으면 즉시 4분할하여 재귀적으로 처리할 수 있도록 if~elif문을 걷어내었다.

import sys
sys.setrecursionlimit(10**6)

n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]
ans = [0,0]
def divide(rs, cs, re, ce):
    global ans, arr
    origin_color = arr[rs][cs]
    size_n = (re - rs) // 2
    size_m = (ce - cs) // 2
    for i in range(rs, re):
        for j in range(cs, ce):
            if arr[i][j] != origin_color:
                divide(rs, cs, rs + size_n, cs + size_m) 
                divide(rs + size_n, cs, re, cs + size_m)
                divide(rs, cs + size_m, rs+ size_n, ce)
                divide(rs + size_n, cs + size_m, re, ce)
                return

    ans[origin_color] += 1

divide(0, 0, n, n)
print(ans[0])
print(ans[1])

 

비슷한 로직을 스택 스타일으로 바꾸어서도 통과를 보았다.

n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]
ans = [0,0]
stack = []
stack.append((0,0,n,n))

while stack:
    isDiff = False
    rs, cs, re, ce = stack.pop()
    origin_color = arr[rs][cs]

    for i in range(rs, re):
        for j in range(cs, ce):
            if arr[i][j] != origin_color:
                isDiff = True
                break
    sr = re - rs
    sc = ce - cs
    if isDiff:
        stack.append((rs, cs, rs + sr // 2, cs + sc // 2))
        stack.append((rs, cs + sc // 2, rs + sr//2, ce))
        stack.append((rs + sr // 2, cs, re, cs + sc // 2))
        stack.append((rs + sr // 2, cs + sc // 2, rs + sr, cs + sc))
    else:
        ans[origin_color] += 1

print(ans[0])
print(ans[1])

 

스택이 76ms, 재귀함수가 56ms 걸린 모습