아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2^k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

🔎 문제 파악

📌 원리는 기본적으로 쿼드트리(참고 : baekjoon_1992 in python)와 동일하다.

📌 주어진 공간이 하나의 문자로 통일되어 있지 않다면 4분할하여 재귀적으로 표현한다.

📌 분열은 쿼드트리 문제와 똑같이 진행하되 global variable로 cnt_white, cnt_blue를 선언하여 카운트를 마치고 모든 재귀함수가 시스템 스택에서 탈출했을 때 출력해주겠다.

🔑 Divide and Conquer

이 역시 분할&정복(Divide and Conquer) 문제이다.

def quadtree(query: list, N: int):
	global cnt_white, cnt_blue
    
	# 입력받은 공간의 문자가 통일 되어 있는지 확인
	if check(query) == 1:
		cnt_blue += 1
		return

	elif check(query) == 0:
		cnt_white += 1
		return
	else:
    	query1, query2, query3, query4 <- 4분할
		
		quadtree(query1, N//2)
		quadtree(query2, N//2)
		quadtree(query3, N//2)
		quadtree(query4, N//2)

공간을 4분할하는 코드도 쿼드트리 문제와 동일하다. 이 역시 간단한 구조이므로 직접 배열의 index를 이용하여 나눠주도록 하겠다.

query1 = [query[line_num][0:N // 2] for line_num in range(N // 2)]
query2 = [query[line_num][N // 2:] for line_num in range(N // 2)]
query3 = [query[line_num + N // 2][0:N // 2] for line_num in range(N // 2)]
query4 = [query[line_num + N // 2][N // 2:] for line_num in range(N // 2)]

🚀 최종 코드

def check(query: list):
	query_temp = ""
	for line in query:
		for char in line:
			query_temp += char
	if "1" in query_temp and "0" not in query_temp:
		return 1

	elif "1" not in query_temp and "0" in query_temp:
		return 0

	else:
		return -1


def quadtree(query: list, N: int):
	global cnt_white, cnt_blue

	if check(query) == 1:
		cnt_blue += 1
		return

	elif check(query) == 0:
		cnt_white += 1
		return

	else:
		query1 = [query[line_num][0:N // 2] for line_num in range(N // 2)]
		query2 = [query[line_num][N // 2:] for line_num in range(N // 2)]
		query3 = [query[line_num + N // 2][0:N // 2] for line_num in range(N // 2)]
		query4 = [query[line_num + N // 2][N // 2:] for line_num in range(N // 2)]

		quadtree(query1, N // 2)
		quadtree(query2, N // 2)
		quadtree(query3, N // 2)
		quadtree(query4, N // 2)


N = int(input())
query = [str(input().strip()).replace(" ", "") for _ in range(N)]
cnt_white, cnt_blue = 0, 0
quadtree(query, N)
print(cnt_white)
print(cnt_blue)