백준(Baekjoon) 1992번 : 쿼드트리 - python 풀이

❓백준(Baekjoon) 1992번 : 쿼드트리

📈 문제 요약

흑백 영상을 압축하여 표현하는 쿼드 트리(Quad Tree)를 활용해 영상을 압축한 결과를 출력하면 되는 문제

🤨 접근법

분할 정복의 대표적인 문제인 쿼드트리 문제이다.

영상 전체가 같은 값이 아니면 해당 영상을 4분할 하여 재귀하는 함수를 구현한다면 출력부분만 시경써서 간단하게 해결할 수 있는 문제이다.

검사하는 구역이 모두 같은 값을 가지면 압축해서 표현 가능하기 때문에 우선 영상 내 모든 값을 검사하는 코드를 배치한다. 이 때 첫 번째 값과 나머지 값을 비교하여 하나라도 틀리게 되면 영상을 4분할 하여 재귀하는 코드로 넘어가도록 한다. 모두 값이 같다면 해당 값을 하나 출력하면 된다.

영상을 4분할 하여 재귀할 때는 다음과 같은 테크닉을 활용할 수 있다.

        n //= 2
        quadtree(r, c, n)
        quadtree(r, c + n, n)
        quadtree(r + n, c, n)
        quadtree(r + n, c + n, n)

이 때 4분할 재귀 전 후로 괄호를 배치해주면 문제에서 제시하는 출력 형태와 같도록 출력이 가능하다.

정리하자면,

• nxn 구역을 검사한다.
• 모두 같은 값을 가진다면 해당 값을 출력한다.
• 하나라도 다른 값이 있다면 4분할 하여 재귀한다.
  • n을 2로 나눠주는 테크닉을 활용할 수 있다.
  • 재귀 전 후로 괄호를 감싸준다.

🔡 코드

import sys

input = sys.stdin.readline

def quadtree(r, c, n):
    
    check = image[r][c]
    for i in range(r, r+n):
        for j in range(c, c+n):
            if image[i][j] != check:
                check = -1
                break
            
    if check == -1:
        print("(", end='')
        n //= 2
        quadtree(r, c, n)
        quadtree(r, c + n, n)
        quadtree(r + n, c, n)
        quadtree(r + n, c + n, n)
        print(")", end='')
    elif check == 1:
        print('1', end ='')
    else:
        print('0', end = '')
    
N = int(input().rstrip())
image = [list(map(int, input().rstrip())) for _ in range(N)]
quadtree(0, 0, N)

📚 고찰

분할 정복의 개념에 대해 정리한 후 처음 맛보는 문제였다. 너무 원자 단위의 문제로 분할하는 데에만 초점을 두고 문제를 풀이해서 압축할 수 있는 부분 까지 분할 후 다시 압축하려고 하니 너무 꼬여서버려서 해결하지 못한 것 같았다.

이번 문제를 통해서 배열을 분할하는 태크닉과 재귀해서 문제를 해결하는 전반적인 방법에 대해서 감을 익힐 수 있었던 것 같다.