[BaekJoon] 백준 1992번 : 쿼드트리

1992번 : 쿼드트리

[BaekJoon] 백준 1780번 : 종이의 개수 문제와 똑같은 문제이다.

차이가 있다면 4등분을 한다는 것과 출력에서 괄호를 더해주는 것이다.

0과 1이 섞여있다면 4등분을 한 뒤 다시 압축을 하게 된다.

이 때 괄호를 더하기 때문에 코드에서도 4등분을 시작 할 때 열린괄호, 4등분이 끝났을 때 닫힌 괄호를 넣어 주면 된다.

---

import sys


def check_arr(width, x, y):

	pivot = arr[x][y]
	for i in range(x, x + width):
		for j in range(y, y + width):
			if pivot != arr[i][j]:
				return [False, -1]
	return [True, pivot]


def do_egg(width, i, j):
	global answer

	check = check_arr(width, i, j)
	if check[0]:
		print(check[1], end='')
		return
	else:
		print('(', end='')
		do_egg(width // 2, i, j)
		do_egg(width // 2, i, j + width // 2)
		do_egg(width // 2, i + width // 2, j)
		do_egg(width // 2, i + width // 2, j + width // 2)
		print(')', end='')


N = int(input())
arr = [[int(x) for x in sys.stdin.readline().rsplit()[0]] for _ in range(N)]
do_egg(N, 0, 0)