[백준 2630] 색종이 만들기 - Python (분할정복, 재귀)

 

2630번: 색종이 만들기

 

 

<내 코드>

 

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

white, blue = 0, 0


def divide(x, y, n):
    global white, blue
    color = paper[x][y]
    check = True

    for i in range(x, x+n):
        if not check:
            break

        for j in range(y, y+n):
            if color != paper[i][j]:
                check = False
                divide(x, y, n//2)  # 1사분면
                divide(x, y+n//2, n//2)  # 2사분면
                divide(x+n//2, y, n//2)  # 3사분면
                divide(x+n//2, y+n//2, n//2)  # 4사분면
                break
    if check:
        if color:
            blue += 1
        else:
            white += 1


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

 

이 문제는 처음 접하는 개념인 '쿼드트리'를 만드는 것이었다. 트리의 자식노드가 4개씩 분할하는 방법이라고 한다.

여기서 분할 된 영역 안에서 같은 색인지 판단해 다르다면 또 다시 나누면서 찾아간다. 일반 동적 계획법과 다르게 분할 정복은 중복되는 하위 문제가 없다는 것이 차이다.