문제 출처 : https://www.acmicpc.net/problem/1992

문제 파악

사각형을 4등분하여
1. 왼쪽 위, 2. 오른쪽 위, 3. 왼쪽 아래, 4. 오른쪽 아래
이렇게 이런식으로 분할하여 만약 같다면 압축할 수 있고 이런 꼴을 쿼드트리라고 하나보다.

어제 풀었던 색종이 만들기 에서 분할-정복 기법을 배웠으니 활용하여 풀어보겠다.

푸는법은 거의 동일했으나, 차이점은 괄호를 언제 열고 닫냐 의 로직이 더 필요했다.
divide() 함수를 실행할때 모든게 같으면 same인데 그렇지 않다면 괄호를 열고 분할 4바퀴를 돌린 후 괄호를 닫아주면 됐다.

import sys
input = sys.stdin.readline

N = int(input())

matrix = []
for _ in range(N):
    matrix.append(input().rstrip())

answer = []

def divide(x,y,size):
    first = matrix[x][y]
    same = True

    # 하나라도 같지 않으면 break,break
    for i in range(x, x+size):
        for j in range(y, y+size):
            if matrix[i][j] != first:
                same = False
                break
        if not same:
            break

   # 다 같으면
    if same:
        answer.append(first)  # first는 '0' 또는 '1'
        return

    # 섞여 있으면 괄호 열고 4분할
    answer.append('(') # 내부 노드 시작 → '('

    half = size // 2
    divide(x,y,half)
    divide(x,y+half,half)
    divide(x+half,y,half)
    divide(x+half,y+half,half)

    answer.append(')') #노드 종료 → ')'

divide(0,0,N)

print(''.join(answer))

리스트 안에 있는 요소들을 리스트 벗기면서 출력할때는
print(answer) 이런식으로 를 사용했는데 이 경우
[123] 이
1 2 3 이렇게 띄어쓰기 되어 나오더라

띄어쓰기 없이 출력하고 싶다면
''.join(answer)
를 활용하자.

다음 날 푼 코드

import sys
input = sys.stdin.readline

N = int(input())

matrix = []
answer = []

for _ in range(N):
    matrix.append(input())

# x,y ~ x+size, y+size 영역에 대해 모두 일치하는 지 검사 , 일치하지 않는다면, 분할하며 들어가며 검사
def divide(x,y,size): 
    global white,blue

    base = matrix[x][y] 
    all_same = True


    for i in range(x, x+size):
        for j in range(y, y+size):
            if base != matrix[i][j]:
                all_same = False
                break
        if not all_same:
            break
    
    # 모두 일치한다면
    if all_same:
        answer.append(base)
        return
    
    # 모두 일치하지 않는다면, 반반씩 쪼개서 divide하며 다시 검사
    half = size//2


    answer.append("(")

    divide(x,y,half) # 왼쪽 위
    divide(x,y+half,half) # 오른쪽 위
    divide(x+half,y,half) # 왼쪽 아래
    divide(x+half,y+half,half) # 오른쪽 아래

    answer.append(")")

divide(0,0,N) # (0,0) , size = N  함수 시 작

prnt(''.join(answer))