N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

I) 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.

II) (I)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (I)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

🔎 문제 파악

📌 분할&정복의 대표적 예시인 쿼드트리(Baekjoon_2630, Baekjoon_1992)와 유사하지만 쿼드트리는 공간을 4등분하는데에 반해 이 문제는 주어진 공간을 총 9등분해야 한다.
->여기서 예상할 수 있는 것이... 쿼드트리처럼 인덱스를 이용해서 분할하는 방식을 그대로 적용한다면 파이썬에서는 시간 초과가 발생할 것이다...

📌 따라서 새로운 배열을 선언하는 방식에서 벗어나 query 배열 하나에서 start position을 조작하는 방식을 사용한다. 이를 위해 x좌표(x)과 y좌표(y)를 단위 공간(unit)간격으로 조작하는 구조가 필요하다.

📌 전역 변수로 cnt 변수들을 선언해주고 입력받은 start postion에서의 단위 공간이 하나의 문자로 통일되어 있다면 해당 cnt 변수에 1을 더한다.

🔑 Divide and Conquer

분할 정복의 구조는 다음과 같다.

def segmentation(x: int, y: int, N: int):
	global cnt_zero, cnt_one, cnt_mione, query
	
    
	if check(x, y, N):
   		# 입력된 단위 공간에 문자가 통일되어 있다면 1을 반환하여 조건문 내부 수행

	else:
		segmentation()

분할&정복을 위해 내부의 segmentation의 parameter는 이중반복문 요소에 의해 컨트롤되는 행과 열에 대한 시작좌표와 9등분된 단위 공간이다.

unit = N // 3

for i in range(3):
	for j in range(3):
		segmentation(x + i * unit, y + j * unit, unit)

다음은 단위 공간 내에 문자가 통일되어 있는 지 확인하기 위한 check함수의 구조다.

def check(x: int, y: int, N: int):
	global query

	tmp = query[y][x]
	for y_pos in range(y, y + N):
		for x_pos in range(x, x + N):
			if query[y_pos][x_pos] != tmp:
				return False
	return True

🚀 최종 코드

def check(x: int, y: int, N: int):
	global query

	tmp = query[y][x]
	for y_pos in range(y, y + N):
		for x_pos in range(x, x + N):
			if query[y_pos][x_pos] != tmp:
				return False
	return True


def segmentation(x: int, y: int, N: int):
	global cnt_zero, cnt_one, cnt_mione, query

	if check(x, y, N):
		tmp = query[y][x]
		if tmp == 0:
			cnt_zero += 1
		elif tmp == 1:
			cnt_one += 1
		elif tmp == -1:
			cnt_mione += 1

	else:
		unit = N // 3

		for i in range(3):
			for j in range(3):
				segmentation(x + i * unit, y + j * unit, unit)


import sys

cnt_zero, cnt_one, cnt_mione = 0, 0, 0
query = []
N = int(input())
for _ in range(N):
	query.append(list(map(int, sys.stdin.readline().split())))

x, y = 0, 0
segmentation(x, y, N)

print(cnt_mione)
print(cnt_zero)
print(cnt_one)

🧐 개선점

ㅎ... 위 알고리즘을 다른 언어로 구현하여 돌려보진 않았지만 일단 파이썬에서는 시간 제한 기준에 아슬아슬하다...
시간 단축을 위한 다른 구조가 있을지 고민해보고 추후 해당 문제의 개선글을 업로드 해보겠다.