[Python] BOJ/백준 2630번 색종이 만들기

[문제]

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

2630번: 색종이 만들기

[풀이]

분할 정복법

: 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복(Conquer)

 

우선 트리의 자식 노드가 4개씩 분할하는 방법을 쿼드 트리라고 한다.

작게 분할한 색종이 안에서 같은 색인지를 판단해 같지 않다면 다시 나누는 과정을 반복한다.

 

첫 번째 나오는 색을 color에 저장한 후 색종이를 돌면서 전체 색이 전부 같은지 확인한다. 

만약 첫 번째 색과 현재 위치의 색이 다르다면 색종이를 4분할로 나눠 cut 함수를 재귀 호출한다.

 

x는 x좌표 시작점, y는 y좌표의 시작점, 세 번째 인자는 색종이의 크기이기 때문에 4사분면의 경우

(x + n // 2, y + n // 2, n // 2)를 인자로 준다.

처음 x, y 는 [0, 0]에서 시작하고 색종이의 크기는 n이기 때문에 메인 함수에서 cut(0, 0, n)을 호출한다.

 

[코드]

import sys

def cut(x, y, n):
    global white, blue
    color = paper[x][y] # 첫 번째 색

    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != paper[i][j]:
                cut(x, y, n // 2)        # 1사분면
                cut(x, y + n // 2, n // 2)      # 2사분면
                cut(x + n // 2, y, n // 2)      # 3사분면
                cut(x + n // 2, y + n // 2, n // 2)    # 4사분면
                return

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

if __name__ == '__main__':
    n = int(sys.stdin.readline())
    paper = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    white, blue = 0, 0
    cut(0, 0, n)
    print(white, blue, sep='\n')