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

 

모두 같은 색이 나올 때 까지 색종이를 잘라서 각각의 종이의 개수를 구하는

분할정복 문제이다.

 

import sys
input = sys.stdin.readline


def f(x, y, N):
    global white, blue
    c = paper[x][y]
    same_color = True
    for i in range(x, x + N):
        for j in range(y, y + N):
            if c != paper[i][j]:
                same_color = False
                break
            if not same_color:
                break
    if same_color:
        if c == 0:  
            white += 1
        elif c == 1:
            blue += 1
    else:
        half = N // 2
        f(x, y, half)
        f(x, y + half, half)
        f(x + half, y, half)
        f(x + half, y + half, half)

N = int(input())
paper = []
blue = 0
white = 0

for i in range(N):
    p = list(map(int, input().split()))
    paper.append(p)

f(0, 0, N)
print(white)
print(blue)

처음으로 현재 보고있는 종이가 모두 같은 색의 요소로 이루어져 있는지 확인한다.

색종이의 첫번째 요소를 그 종이의 색으로 지정하고, 다른 요소들을 체크하여 만약 다른 색이 있다면

same_color에 False를 반환해준다. 모두 같은 색이라면 카운팅 해준다.

 

same_color가 False일 때 가로, 세로 각각 절반을 기준으로 나눠서

네 번의 재귀호출을 해준다.