[백준 -1992] 쿼드트리

❓ Problem

🤔 How

여담으로 이러한 쿼드트리 방식은 실제 비디오 압축, 등 여러 압축기술에 사용된다 !

문제를 보고 딱 분할정복 문제이다 싶었는데 어떻게 구현하는지 살짝 먹먹 했는데 다행이 잘 해결했다. 😅 구현, 분할정복 문제를 익숙하게 할수있도록 연습해야겠다.

1. 수학의 사분면을 이해하고 접목해야한다. 쿼드트리 지문에 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축 으로 명시되어 있다.

2. 행열을 탐색하며 처음 글자와 비교했을때 다른글자가 있으면 시작점을 기준으로 4분면을 나누고 작은단위로 쪼개면서 다시 압축여부를 판별해야한다.

3. compression 함수 해당함수는 압축하는 함수임과동시에 재귀적으로 호출하여 분할정복을 실제 실행하는 함수이다. 행열 탐색중 다른 글자를 찾게된다면 4분면을 기준으로 다시 쪼개서 탐색한다.

❗ Solve

# 쿼드트리
import sys

input = sys.stdin.readline


def get_board(rows):
    return [input().strip() for _ in range(rows)]


def solution():
    l = int(input())
    board = get_board(l)
    answer = ""

    def compression(y, x, l):  # 압축
        nonlocal answer
        start = board[y][x]
        for row in range(y, y + l):
            for col in range(x, x + l):
                if board[row][col] != start:
                    l //= 2
                    answer += "("
                    compression(y, x, l)
                    compression(y, x + l, l)
                    compression(y + l, x, l)
                    compression(y + l, x + l, l)
                    answer += ")"
                    return
                    pass
        answer += start

    compression(0, 0, l)
    print(answer)
    pass


if __name__ == "__main__":  # 실행되는 부분
    solution()
    pass