백준 알고리즘 2630 (색종이 만들기) - python

백준 알고리즘 2630 (색종이 만들기) - python

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

2630번: 색종이 만들기

 

4-분할 정복!

4분할을 하여 한 사분면이 모두 같은 색일 때까지 분할하여 카운트하는 방법

 

[문제 풀이]

1. 기준 색을 받는다.

2. 맵을 탐색하며 모두 같은 색인지를 확인한다.

3. 모두 같지 않다면 4분할을 재귀적으로 시도한다.

4. 모두 같은 색인 경우는 이중 for문 이후의 부분이다.

5. 그 때의 색종이 갯수를 카운트한다.

* blue와 white 배열 내에는 분할된 종이 조각들의 면적이 저장되어 있을 것이다.

   sum(blue) + sum(white) = N ** 2의 전체 면적일 것.

 

import sys
N = int(sys.stdin.readline())
_map = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
blue = []
white = []

def div_and_conq(x, y, n):
    color = _map[x][y] # 기준 색
    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != _map[i][j]: # 하나라도 다르면
                # 4 분할
                div_and_conq(x, y, n // 2)
                div_and_conq(x + n // 2, y, n // 2)
                div_and_conq(x, y+ n // 2, n // 2)
                div_and_conq(x + n // 2, y + n // 2, n // 2)
                return
    # 모두 같은 색인 경우
    if color == 1:
        blue.append(n ** 2)
    else:
        white.append(n ** 2)
    return

div_and_conq(0, 0, N)
print(len(white))
print(len(blue))