흑백 영상을 압축하여 표현하는 데이터 구조로 "쿼드 트리(Quad Tree)" 라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다. N × N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

🔎 문제 파악

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

📌 공간을 분할하기 전에 여는 괄호 "("를 입력하고 분할된 공간 압축을 완료하면 닫는 괄호 ")"를 입력한다.

📌 분할되어진 공간이 모두 "0" 혹은 "1"로 통일된다면 해당 문자로 압축한다.

🔑 Divide and Conquer

문제를 푸는 열쇠는 역시 분할&정복(Divide and Conquer)이다.

def quadtree(query: list, N: int):
	# 입력받은 공간의 문자가 통일 되어 있는지 확인
	if check(query, N) == 0:
		print("0", end="")
		return

	elif check(query, N) == 1:
		print("1", end="")
		return

	else:
    	query1, query2, query3, query4 <- 4분할
		
        print("(", end="")
		quadtree(query1, N//2)
		quadtree(query2, N//2)
		quadtree(query3, N//2)
		quadtree(query4, N//2)
		print(")", end="")

사용자로부터 배열을 2차원 배열 형태로 입력받는다.

N = int(input())
query = [list(input().strip()) for _ in range(N)]

2차원 배열을 4분할하는 형태는 배열의 인덱스를 이용해서 어렵지 않게 구현이 가능하다.

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):
	if check(query) == 1:
		print("1", end="")
		return

	elif check(query) == 0:
		print("0", end="")
		return

	else:
		print("(", end="")

		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)
		print(")", end="")

N = int(input())
query = [list(input().strip()) for _ in range(N)]
quadtree(query, N)