백준 2630번 - 색종이 만들기

문제 출처 : https://www.acmicpc.net/problem/2630

코드

import sys

N = int(input())
MAP = []
for i in range(N): MAP.append(list(map(int, sys.stdin.readline().split())))

result = []
def divide(size, x1, y1, x2, y2):
    if size >= 1:
        b, w = 0, 0
        for i in range(x1, x2):
            for j in range(y1, y2):
                if MAP[i][j] == 1:
                    b += 1
                if MAP[i][j] == 0:
                    w += 1

        if b == size**2:
            result.append("b")
            return

        if w == size**2:
            result.append("w")
            return

        else:  
            divide(size//2, x1, y1, x1 + size//2, y1 + size//2)
            divide(size//2, x1, y1 + size//2, x1 + size//2, y1 + size)
            divide(size//2, x1 + size//2, y1, x1 + size, y1 + size//2)
            divide(size//2, x1 + size//2, y1 + size//2, x1 + size, y1 + size)
            
    
divide(N, 0, 0, N, N)
print(result.count("w"))
print(result.count("b"))

풀이

재귀를 통해서 작은 단위에서 색종이가 나뉘는지 판단한 뒤, 더 작게 나눌 수 있으면 다시 재귀를 통해 size의 절반 크기로 함수를 호출하고, 더 작게 나눌 수 없다면 해당 색종이가 하얀색인지 파란색인지 판단하여 개수를 누적한다. 마지막에 누적된 색상의 개수를 각각 출력한다.

여러 분할 정복 문제를 풀어보면 이러한 방법이 해당 알고리즘의 일반적인 풀이 구조 인 것 같다. 역시 기초를 잘 다지는 것이 중요,,