[python] 백준 2630 - 색종이만들기

백준 2630 - 색종이 만들기 [SILVER 2]

1과 0으로 이루어진, 길이가 똑같은 2차원 배열이 들어온다.
N/2 길이의 2차원 배열로 내부를 나눌 때, 나눈 배열 안이 한 가지 수로만 이루어져 있으면
해당 색깔 (1: 파랑, 0: 하양) 색종이가 완성된 것으로 친다.
모든 부분을 나누었을 때, 각각 완성된 색종이는 몇 개인가?

쿼드트리 분할정복

2차원 배열을 사분면으로 쪼개어 해당 부분 내에서 조건을 만족하면 return

그렇지 않으면 다시 사분면으로 쪼개어 계속해서 조건을 만족하는지 확인한다.

4개로 쪼갠 사분면 내부를 검증할 때 범위를 어떻게 설정해주는지가 가장 중요한 것 같다.

정답 코드

import sys

input = sys.stdin.readline

N = int(input())

paper = [list(map(int, input().split())) for _ in range(N)]

def graph(n, m, paper):
    global b, w
    # 순회하면서 1, 2, 3, 4분면을 검증한다.
    for dx, dy in [(n, 0), (0, 0), (n, n), (0, n)]:
        check = 0
        for y in range(dy, dy+n):
            check += sum(paper[y][dx : dx+n])
        if check == m:
            b += 1
        elif check == 0:
            w += 1
        else:
            # 더욱 작은 면을 검증하기 위해
            # 변의 길이, 원소의 수, 해당 사분면으로 축소한 종이를 인자로 재귀한다
            graph(n//2, m//4, [paper[y][dx : dx+n] for y in range(dy, dy+n)])


# 쪼갤 필요 없이 통일된 경우 체크
f = sum([sum(p) for p in paper])

if f == N**2:
    print(f'{0}\n{1}')
elif not f:
    print(f'{1}\n{0}')

# 쪼개야하는 경우 함수 시작
else:
    n = N//2
    m = N**2 // 4
    b,w = 0,0
    graph(n, m, paper)
    print(f'{w}\n{b}')

결과는 다음과 같다.

메모리	시간	코드길이
31120kb	56ms	690B