[Python] Baekjoon1992: 쿼드트리

쿼드트리

2 초

128 MB

26291

16169

12685

60.909%

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(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의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

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

풀이

색종이 문제와 비슷한 원리로 풀이할 수 있습니다.

차이점은 만약 현재 사각형이 4개로 쪼개지지 않는다면 그냥 숫자로 나타내지만

쪼개진다면 (소괄호)로 감싸주어야 한다는 것입니다.

 

입력값 받아주기

입력값은 그냥 문자열 그대로 받아서 리스트에 넣었습니다.

N = int(input())
lst = []

for i in range(N):
    lst.append(input()) # 문자열이 들어갑니다

 

메소드 구성

주어진 영상의 크기 N을 메소드의 인자로 넘겨줍니다. 매 재귀마다 현재 영상의 크기를 바로 알 수 있습니다.

1) 모두 같은 색인지 확인하기

현재 영상의 맨 왼쪽 위의 한 점을 추출해서 그 값을 저장합니다 (0이거나 1).

현재 영상의 탐색 시작점을 row, col이라고 했을 때 그 점을 기준으로 N크기만큼 탐색합니다.

처음의 추출한 값과 달라진다면 4갈래로 쪼개주어야합니다. 불린 변수를 하나 지정해서 값이 달라지면 값이 바뀌도록 합니다.

def dfs(row, col, N): # N은 영상의 크기
    global lst # 리스트의 정보를 가져옴

    S = lst[row][col] # 글자 추출
    
    judge = True # 하나라도 다른게 있다면 False로 바꿈
    
    L = '' //초기 문자열
    
    # 모두 같은 색인지 검사하는 부분
    for i in range(N):
        for j in range(N):
            if S != lst[row+i][col+j]:
                judge = False # 다르다면? False
                break

 

2) 소괄호 넣기

만약 4갈래로 나눌 필요가 없다면? 그냥 0이나 1을 출력하면 됩니다. (judge = True)

하지만 나눠야한다면 소괄호로 감싸주고 그 안에서 재귀를 호출합니다. (judge = False)

    if judge:
        L = S
    else:
        L = '('+dfs(row, col, N // 2)+dfs(row, col + N // 2, N // 2)+dfs(row + N // 2, col, N // 2)+dfs(row + N // 2, col + N//2, N // 2)+')'

 

전체 코드

def dfs(row, col, N): # L은 글자
    global lst

    S = lst[row][col] # 글자 추출
    judge = True
    L = ''
    # 모두 같은 색인지 검사하는 부분
    for i in range(N):
        for j in range(N):
            if S != lst[row+i][col+j]:
                judge = False
                break
    if judge:
        L = S
    else:
        L = '('+dfs(row, col, N // 2)+dfs(row, col + N // 2, N // 2)+dfs(row + N // 2, col, N // 2)+dfs(row + N // 2, col + N//2, N // 2)+')'

    return L

N = int(input())
lst = []

for i in range(N):
    lst.append(input()) # 문자열이 들어갑니다

print(dfs(0, 0, N))