BOJ 2630 - 색종이 만들기

문제

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

 

 

풀이

분할 정복으로 문제를 해결한다

 

(0~n, 0~n) 구역이 모두 같은 색이면 해당 색깔의 종이 수를 1 더하고 함수를 종료한다

모두 같은 색이 아니라면 다음 4구역으로 나눈 후 각 구역에서 모두 같은 색인지 확인한다

(0~n/2, 0~n/2)

(n/2~n, 0~n/2)

(0~n/2, 0/2~n)

(n/2~n, n/2~n)

 

 

코드

python

def solve(y, x, n):
    global white, blue
    reference_color = color_paper[y][x]
 
    for i in range(y, y + n):
        for j in range(x, x + n):
            if reference_color != color_paper[i][j]:
                solve(y, x, n // 2)
                solve(y, x + n // 2, n // 2)
                solve(y + n // 2, x, n // 2)
                solve(y + n // 2, x + n // 2, n // 2)
                return
 
    if reference_color == 0:
        white += 1
    else:
        blue += 1
 
 
white = 0
blue = 0
 
n = int(input())
color_paper = [list(map(int, input().split())) for _ in range(n)]
 
solve(0, 0, n)
print(white)
print(blue)