[Python] BOJ 2630 - 색종이 만들기(분할 정복)

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

2630번: 색종이 만들기

* 분할 정복이란?

   - 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법

 

분할 정복에도 여러가지 종류가 있지만, 이 문제는 쿼드트리(quad-tree)를 통해 풀어 보았다.

 (https://www.acmicpc.net/problem/1992  백준에는 쿼드트리 문제도 있지만, 이 문제가 더 쉽다)

 

 

import sys
input = sys.stdin.readline
n = int(input())
Map,line = [],[]
blue,white = 0,0
for i in range(n):
    Map.append(list(map(int,input().split())))
def quad_tree(n,x,y):
    global blue
    global white
    color = Map[x][y]
    for i in range(x,x+n):
        for j in range(y,y+n):
            if(Map[i][j] != color):
                color = -1
                break
        if(color == -1):
            break
    if(color == 0):
        white += 1
    elif(color == 1):
        blue += 1
    elif(color == -1):
        quad_tree(n//2,x,y)
        quad_tree(n//2,n//2+x,y)
        quad_tree(n//2,x,n//2+y)
        quad_tree(n//2,n//2+x,n//2+y)
quad_tree(n,0,0)
print(white)
print(blue)

기준값인 Color를 Map[x][y]로 설정하고 n x n 크기의 정사각형만큼의 범위를 이중for문으로 체크하면서 Map[x][y]와 기준값이 같은지 확인해서 하나라도 다르면 color에 -1을 넣고 break를 걸어주었다.

모두 같으면 color가 모두 1이거나 0이므로 white나 blue에 1을 더해주었고 color가 -1이면 Map을 4분할한다음 각 사분면마다 재귀함수로 quad_tree함수를 실행시켜주었다.

* 예제입력과 같은경우에는 n이 8이므로 처음에 Map[0][0]부터 Map[7][7]까지 확인해서 1과 다른 칸이 하나이상 있으므로 color에 -1을 넣고 quad_tree(4,0,0), quad_tree(4,4,0), quad_tree(4,0,4), quad_tree(4,4,4)를 실행한다. 그 뒤로는 이와 같다.