[BOJ/Python] 1992_쿼드트리

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

1992번: 쿼드트리

문제

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

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

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

입력

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

출력

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

예제 입력 1

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

예제 출력 1

((110(0101))(0010)1(0001))

---

풀이

 

문제 풀이과정은 다음과 같다.

1. 현재 탐색하는 영역이 모두 0 또는 모두 1로 이루어져있는가?
2. 그렇다면 모두 0이라면 0을 반환하고, 모두 1이라면 1을 반환한다.
3. 모두 0 또는 모두 1이 아니라면, 4등분을 하여 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 부분으로 나눈다.
4. 영역을 나눌 때, '('를 추가하고, 4 등분한 영역을 모두 탐색하고 나면 ')'를 추가하여 닫아준다.
5. 나눈 부분에 대하여 1~3의 과정을 반복한다.

문제에서 주어진 그림을 통해 살펴보면 다음과 같다.

 

흰색 부분은 1이고, 회색 부분은 0이다. (실수로 문제와 반대로 표를 만들어버렸다.. ㅠㅠ 하지만 과정은 똑같다..)

문제에서 결과가 (0(0011)(0(0111)01)1) 나왔으므로, (1(1100)(1(1000)10)0)의 결과가 나오는 과정을 살펴보자.

첫째로 우리가 살펴볼 영역은 이 전체 영역이고, 모두 같은 색이 아니므로 4등분 해준다.

 

빨간 선 기준으로 4 등분된 영역을 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 살펴본다.

우선 4등분을 하였으므로 현재 상태는 ( 이다.

 

왼쪽 위의 영역을 살펴봤을 때, 모두 하얀색이므로 1이 된다.

따라서 현재 상태는 (1 이다.

오른쪽 위의 영역을 살펴봤을 때, 모두 같은 색이 아니므로 다시 4등분을 한다.

따라서 현재 상태는 (1( 이다.

4등분을 한 빨간 선 기준으로 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래를 각각 살펴봤을 때 모두 같은 색이므로 각각의 영역에 해당하는 수인 1,1,0,0을 반환하고, )를 닫아준다.

따라서 현재 상태는 (1(1100) 이다.

이제 왼쪽 아래 영역을 살펴보면 영역의 색이 모두 같지 않기 때문에, 4등분을 해준다.

따라서 현재 상태는 (1(1100)( 이다.

4 등분한 영역을 순서대로 살펴봤을 때, 왼쪽 위의 경우 모두 색이 1로 같기 때문에 1이 된다.

따라서 현재 상태는(1(1100)(1 이다.

 

오른쪽 위 영역의 경우, 모두 색이 같지 않기 때문에 4등분을 해준다.

현재 상태는 (1(1100)(1( 이다.

4등분을 한 영역을 각각 살펴봤을 때, 각 영역의 색이 일정하므로 각 영역의 색을 반환하고 괄호를 닫아준다.

현재 상태는 (1(1100)(1(1000) 이 된다.

 

왼쪽 아래와 오른쪽 아래를 살펴봤을 때, 영역의 색이 일정하다.

따라서 현재 상태는 (1(1100)(1(1000)10)이 된다.

마지막 오른쪽 아래의 경우, 색이 하나로 일정하므로 최종 결과는 다음과 같다.

(1(1100)(1(1000)10)0)

 

문제에서는 흰색을 0, 검은색을 1로 하였다. 방법은 같으니 반대로 생각하면 이해할 수 있을 것이다...

코드는 다음과 같다.

 

import sys
 
def quad_tree(result,grid,n):
    flag_1 = False
    flag_0 = False
    for i in range(n):
        if '1' in grid[i]:
            flag_1 = True
        if '0' in grid[i]:
            flag_0 = True
        if flag_1 and flag_0:
            break
    if flag_1 and not flag_0:
        return result+'1'
    elif not flag_1 and flag_0:
        return result+'0'
    else:
        result+='('
        grid1 = [grid[i][:n//2] for i in range(0,n//2)]
        grid2 = [grid[i][n//2:] for i in range(0,n//2)]
        grid3 = [grid[i][:n//2] for i in range(n//2,n)]
        grid4 = [grid[i][n//2:] for i in range(n//2,n)]
        
        result = quad_tree(result,grid1,n//2)
        result = quad_tree(result,grid2,n//2)
        result = quad_tree(result,grid3,n//2)
        result = quad_tree(result,grid4,n//2)
 
        return result+')'
 
 
n = int(sys.stdin.readline())
 
grid = []
for _ in range(n):
    grid.append(list(sys.stdin.readline().strip()))
 
result = ''
result = quad_tree(result,grid,n)
 
print(result)

• result의 경우, 최종적으로 출력할 문자열이다. 위의 예시의 경우, (1(1100)(1(1000)10)0) 이 된다.
• grid는 현재 살펴볼 영역이고, 만약 현재 영역의 색이 모두 1 또는 0이 아니라면 '('를 추가하고, 영역을 4 등분한 뒤, 그 영역에 대하여 탐색을 한 후 ')'를 추가한 값을 반환한다.