백준 - 색종이 만들기(2630번 Python 풀이)

이 색종이 만들기 문제는 백준에서는 분할 정복 알고리즘으로 분류되어 있다.

여기서 분할 정복 알고리즘은 기본적으로 엄청나게 크고 방대한 문제를 조금씩 나눠가면서 푸는 문제인데

재귀 함수랑 비슷하다고 생각이 들어 재귀함수처럼 함수 내에서 자기 자신의 함수를 호출하여 푸는 방식으로 알고리즘을 생각해보았다.

 

풀이

import sys
input = sys.stdin.readline

n = int(input())

bd = [list(map(int, input().split())) for _ in range(n)]

result = []

def d(x, y, n):
	color = bd[x][y]
	for i in range(x, x+n):
		for j in range(y, y+n):
			if color != bd[i][j]:
				d(x, y, n//2)
				d(x, y+n//2, n//2)
				d(x+n//2, y, n//2)
				d(x+n//2, y+n//2, n//2)
				return
	if color == 0:
		result.append(0)
	else:
		result.append(1)

d(0,0,n)
print(result.count(0))
print(result.count(1))

d라는 함수를 선언해주고 반복문을 통해 서로 다른 숫자가 없는지 계속 검사해주고 그 수를 리스트에 추가해 count함수를 이용해 값을 출력해냈다.