색종이 만들기

백준 2630

분할정복

: 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는다.

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

white = 0
blue = 0

def quad_tree(x, y, n):
    global white, blue
    flag = 0
    color = paper[x][y]

    for i in range(x, x+n):
        for j in range(y, y+n):  
        #처음 color와 다르면 flag++
            if color != paper[i][j]:
                flag += 1
                break
    #조건이 만족되지 않을 시에는 쪼개어서 푼다.
    if flag != 0:
        quad_tree(x, y, n//2) #1사분면
        quad_tree(x, y+n//2, n//2) #2사분면
        quad_tree(x+n//2, y, n//2) #3사분면
        quad_tree(x+n//2, y+n//2, n//2) #4사분면

    else: 
        if color == 0:
            white += 1
        else:
            blue += 1

quad_tree(0,0,n) #(0,0)부터 시작
print(white)
print(blue)

전역변수를 쓰는게 좋지 않다고 해서 다음부터는 파라미터로 넘겨주도록 해야겠다. 조건에 맞고 안맞고를 기록하는 것은 flag변수를 통해서 했고 조건에 맞지 않으면 재귀를 통해 범위를 줄여나가면서 진행했다.

그림 참고