Baekjoon Training #2630

---

#2630 색종이 만들기

import sys
input = sys.stdin.readline  # 시간단축용

n = int(input())    # 색종이 변의 길이
base = [list(map(int,input().split())) for _ in range(n)]   # 색 베이스를 2차원 배열로 세팅
ans_list = []   # 정답을 담을 ans_list 초기화

# 색 구분하는 check함수
def check(x, y, n):
    color = base[x][y]    # 시작점 색을 기준점으로 설정
    # 2중 for문을 통해 전체 색 조사
    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != base[i][j]:   # 확인중인 칸의 색이 기준점 색과 다르면
                n2 = n//2   # 길이 절반을 세팅
                # 네개의 구역으로 나누어 재귀호출
                check(x, y, n2)
                check(x, y+n2, n2)
                check(x+n2, y, n2)
                check(x+n2, y+n2, n2)
                return
    # 재귀호출을 할 조건이 아닐때 (해당 구역에 같은 색만 존재할때)
    # 해당 색을 정답 리스트에 입력
    if color == 0:
        ans_list.append(0)
    else:
        ans_list.append(1)

# 함수 실행후 정답 리스트에서 두가지 색 각각 카운트
check(0,0,n)
print(ans_list.count(0))
print(ans_list.count(1))

정사각형 범위를 전수조사하여 다른 색이 섞여 있다면 사분할 하여 재귀호출하는 함수가 핵심이다.

색종이의 길이가 2,4,8,16,32,64,128로 주어졌다는 점에서 범위도 적절하게 조절되어있고 2의 제곱수로 이루어져 있어서 계속해서 사분할을 하여도 문제가 생기지 않도록 적절한 길이만 주어져있다.

사분할을 반복하다가 조사 구역의 색이 모두 같으면 재귀호출을 멈추고 해당 색을 정답 리스트에 담아둔다. 추후에 정답 리스트에서 0과 1로 설정되어 있는 색의 수를 counting하면 정답을 쉽게 출력할 수 있다.

---