[백 준/DFS/BFS] 1992: 쿼드트리

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

핵심 아이디어

• 분할 정복 -> 재귀 또는 스택으로 구현. 
• 분할 정복이란 큰 문제를 하위문제로 나눠 풀어 상위 문제를 푸는 개념
• 재귀함수 - 로직은 같은데 매개변수가 변하는 것. 여기서는 분할 할 때 범위만 줄어든다. n = n // 2

풀이

n = int(input())
graph = []
for _ in range(n):
	graph.append(list(map(int, input())))

# 분할정복
def daq(x,y,n):
	check = graph[x][y]
	for i in range(x, x+n):
		for j in range(y, y+n):
			if check != graph[i][j]: # 즉 같은 색으로만 이루어지지 x
				check = -1
				break

	# 분할 정복은 재귀적으로 푼다. 로직은 같은데 매개변수만 변하는 것
	if check == -1: # 분할한다.
		print('(', end='')
		n = n // 2
		daq(x, y, n)
		daq(x,y+n, n)
		daq(x+n, y, n)
		daq(x+n, y+n, n)
		print(')', end='')
	elif check == 1:
		print(1, end='')
	else:
		print(0, end='')

daq(0,0,n)

위 왼쪽, 위 오른쪽, 아래 왼쪽, 아래 오른쪽 순으로 호출해야합니다.

참고 블로그

https://zidarn87.tistory.com/382

파이썬 / BOJ 백준 / 1992 쿼드트리 - 분할정복