소스코드

import sys
input = sys.stdin.readline
N = int(input().strip())
graph = [list(map(int, input().strip().split())) for _ in range(N)]
result = [0,0] # 하얀색, 파란색 색종이 개수

def solve(size, x, y):
	global result
	
	# 현재 사이즈에서 정사각형을 만족하는지 확인
	standard_color = graph[x][y]
	is_same = True
	for i in range(x, x + size):
		for j in range(y, y + size):
			color = graph[i][j]
			
			# 기준 색깔과 다른 경우
			if color != standard_color:
				is_same = False
				break
		if not is_same:
			break
	
	# 정사각형 사이즈 내에서 모든 색이 동일한 경우
	if is_same == True:
		result[standard_color] += 1
	else:
		# 모든 색이 동일하지 않은 경우
		half = size // 2
		solve(half, x, y) # 1사분면
		solve(half, x, y + half) # 2사분면
		solve(half, x + half, y) # 3사분면
		solve(half, x + half, y + half) # 4사분면

print('\\n'.join(map(str, result)))

import sys
input = sys.stdin.readline
N = int(input().strip())
graph = [list(map(int, input().strip().split())) for _ in range(N)]
result = [0,0] # 하얀색, 파란색 색종이 개수

def solve(x,y,size,result):
	color = graph[x][y]
	
	# 정사각형 사이즈 내에서 하나라도 색이 맞지 않으면 재귀호출(4분면으로 영역을 나눠서)
	for i in range(x, x + size):
		for j in range(y, y + size):
			if graph[i][j] != color:
				half = size // 2
			
				solve(x,y, half, result)
				solve(x, y + half, result)
				solve(x + half, y, result)
				solve(x + half, y + half, result)
				return
	
	if color == 0:
		result[0] += 1
	else:
		result[1] += 1
		
solve(0,0,N,result)
print(f"{result[0]}\\n{result[1]}")

풀이

• 전형적인 재귀 문제입니다.
  • 같은 로직이 반복될 것 같이 느껴지는 문제입니다.
• 정사각형 영역의 좌측 상단 첫번째 좌표를 이용해서 기준 색깔을 하나 정하고, 인자로 넘겨준 size 내에서 동일 색이 아닌 사각형이 등장하면 4개의 영역으로 나눠서 재귀호출을 진행합니다.
  • 이때 x,y(정사각형 영역의 첫번째 사각형 좌표), size(정사각형의 크기)를 넘겨줘야 재귀적으로 호출되었을 때도 다시 영역을 분리하거나 색이 동일한지 확인 할 수 있습니다.
• result 리스트를 만들어서 하얀색과 파란색종이의 개수를 한 변수에서 관리합니다.

복기

• 왜이리 조건을 잘게 잘랐을까?
• 시간 제한을 걸어두고 풀면 자꾸 분기를 많이 쪼개나가는 것 같다.
  • 자꾸 세분화하는 느낌?
  • 쓸데없는 분기가 많다
• 좀 더 여유를 두고 큰 관점에서 바라보고 싶은데 쉽지 않다!
  • 다시 풀어보면서 다음 복기 때는 또 어떻게 풀어내는지 봐야겠다