[백준] 1992번 [재귀] 쿼드트리

📌 [백준 1992번 쿼드트리]

개념

재귀함수
호출한 함수 안에서 그 함수를 다시 호출함(recursive call)으로 반복하는 것을 의미한다. 보통 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많다. 파이썬에서는 최대 재귀 깊이가 1,000으로 정해져 있으므로 재귀호출을 사용하려면 반드시 종료 조건을 만들어 주어야 합니다. 재귀함수는 FILO 방식대로 호출됩니다.

def factorial(n):
    if n == 1:      # n이 1일 때
        return 1    # 1을 반환하고 재귀호출을 끝냄
    return n * factorial(n - 1)    # n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함
print(factorial(5)) # 120

문제

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

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

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


쿼드트리란?

• 트리 자료구조중 하나로 부모 노드 아래에 자식 노드를 4개(Quad)씩 가지고 있는 트리입니다.

쿼드트리 알고리즘이란?

• 각 레벨(깊이)에서 현재의 평면을 4개로 쪼개고 각 쪼개어진 4개의 영역에 대해 유사성을 검증하여 하나의 영역으로 묶는다거나 등 필요한 과정을 처리할 수 있고, 또는 쪼개어진 영역을 또 4개의 영역으로 쪼개어 재귀호출을 더 할 수 있습니다. 공간을 분할시켜 각 영역에 대해 처리하고자 하는 알고리즘을 적용시키는 방법이 쿼드 트리 적용 알고리즘입니다. 쿼드트리 방식이란 공간을 4분할 하라는 것입니다.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

나의 풀이

n = int(input())
video = []
result = ""
for i in range(n):
    video.append(list(input()))

def div(x,y,size):
    global result
    loop = True
    check = video[x][y]
    for i in range(x,x+size):
        for j in range(y,y+size):
            if video[i][j]!=check:
                loop = False
                result += "("
                size //= 2
                div(x, y, size)
                div(x, y + size, size)
                div(x + size, y, size)
                div(x + size, y + size, size)
                result += ")"
                break
        if not loop:
            break
    if loop:
        result+=video[x][y]

    return result
print(div(0,0,n))

 

1. 입력으로 영상의 크기를 n으로 받는다.
2. 0과 1로 이루어진 영상을 video로 정의한다.
3. 결과를 출력하기 위해 전역변수로 result를 선언합니다.
4. 영상의 크기만큼 한 줄씩 리스트로 만들어서 넣습니다. (∵ 영상의 크기는 2차원 배열이므로)
5. 범위안에 한 개라도 다른 경우가 있으면 4분면으로 나눠서 다시 검색해야 하는 반복적인 작업을 하므로 div라는 재귀 함수를 선언하여 호출하였습니다. 영상이 모두 1 또는 0으로 이루어졌는지 확인하기 위해서 첫 색깔을 check에 넣어 준다. (∵ 첫 색깔과 나머지 색이 같아야 하므로) loop은 for 문 탈출용과 압축한 값을 넣기 위한 구분 값으로 선언하였습니다.
6. 4등분한 범위안에 나머지 색들을 check 와 비교하여 만약 색이 다른 값이 존재하면 모두 1 또는 0으로 이루어져 있지 않습니다. size를 4등분하기 위해 2로 나누고 div를 2, 1, 3, 4 사분면 순으로 호출하고 for 문을 나갑니다. 4개의 영역을 압축한 결과를 괄호로 묶어서 표현해야 하므로 시작과 끝에 괄호를 열고 닫습니다.
7. loop가 False일 때 for 문을 나갑니다.
8. loop가 True이면 1 또는 0으로 이루어져 있으므로 result에 압축한 결과를 넣습니다.
9. 재귀를 다 호출한 후에는 result를 리턴합니다.