[BOJ] [Python] 2630 : 색종이 만들기

분할정복 알고리즘을 이용했다.

 

분할정복 알고리즘의 로직은 다음과 같다.

 

1.  문제가 분할이 가능하면, 2개 이상으로 나눈다.

2.  나누어진 문제가 여전히 분할 가능하면 1번을 다시 수행하고, 가능하지 않다면 문제를 푼다.

3. 나누어진 각각을 모두 합병한다.

 

 

이 문제는 해결이 가능할 때까지 반복해서 4등분으로 나눈다.

즉, 계속 쿼드 트리를 만드는 것이다. 

 

(쿼드 트리는 트리의 자식 노드가 4개인 트리를 뜻한다.)

 

 

어떻게 4등분을 할지 생각해보자.

 

좌표

 

색종이는 항상 정사각형이기 때문에,

4등분을 하고 각 왼쪽 위을 기준으로 재귀함수를 돌리는 것을 반복한다.

 

 

 

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

w = 0
b = 0


def quad_tree(x, y, n):
    global w, b

    check = graph[x][y]

    for i in range(x, x + n):
        for j in range(y, y + n):
            if check != graph[i][j]:

                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사분면
                return

    if check == 0:
        w += 1
        return

    else:
        b += 1
        return


quad_tree(0, 0, num)

print(w)
print(b)

 

만약 정사각형 내 색깔이 하나로 통일된다면, 어떤 색깔인지 체크하고 다음 사분면으로 넘어간다.

현재 n을 기준으로 1, 2, 3, 4분면을 모두 체크했다면, 부모노드의 n으로 돌아간다.

 

 

 

+ 참고

 

https://blog.naver.com/maelblood/20168518863

 

최상위 노드에서 1/4 한다면 쿼드 트리가 만들어진다.

쿼드 트리에서 다시 1/4 해서, 8개의 노드를 가지는 것은 옥트리라고 한다.