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

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

2630번: 색종이 만들기

• 분할 정복
• 재귀

분할정복이란 간단히 말해서 큰것에서 작은것을 탐색하고 최소단위에 도달하면 순차적으로 모든 값을 리턴하는 것이다.

이 색종이 문제는 분할 정복의 기본이라 할 수 있다.

 

입력받은 n을 2로 계속 나누어 네 개의 부분으로 나눌 수 있다.

백준 2630

 

그 n을 2로 나눈 것을 4번 재귀호출 하고 반복문을 돌려 나눠진 범위 내의 숫자가 모두 같다면 judge = True로 다르다면 False로 판단하여 False이면 최소 단위가 되거나 그 범위의 숫자가 같을 때 까지 재귀를 하고 True이면 알맞은 색깔을 += 1 하면 된다.

 

개념만 이해하면 코드 구현은 간단하다

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int,input().split()))for _ in range(n)]
white = 0
blue = 0

def recursive(num,col,row):
    global white
    global blue
    thisTile = arr[col][row]
    if num == 1:
        if thisTile == 0:
            white += 1
        else:
            blue += 1
        return
    judge = True

    for i in range(num):
        for j in range(num):
            if arr[col+i][row+j] != thisTile:
                judge = False

    if judge:
        if thisTile == 0:
            white += 1
        else:
            blue += 1

    else:
        num = num // 2
        recursive(num,col,row)
        recursive(num,col+num,row)
        recursive(num,col,row+num)
        recursive(num,col+num,row+num)


recursive(n, 0, 0)

print(white)
print(blue)