백준 알고리즘 - 쿼드트리 (1992) [Python]

 

 

 문제

 

www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

 

 

 

 

 

 문제 상황

 

- 0과 1로 이루어진 2차원 배열을 압축하며 압축이 불가능할 경우 4분할하여 작업을 반복한다.

 

 

 

 

 

 

 

 해결 전략

 

- 재귀를 이용하여 주어진 조건을 분할정복한다. 요소가 전부 한가지로 되어있으면 괄호가 없이 해당 숫자를 출력하고 0과 1이 모두 존재하면 다시 4분할하며 작업을 반복한다. 이 때, 괄호를 넣어주어야 한다.

 

1. 모든 요소를 검사하며 0행 0열의 값을 기준으로 다른 값이 하나라도 나오면 4분할을 진행한다. 4분할을 진행할 때에 결과에 괄호를 쳐준다.

 

2. 만약 모든 요소가 같다고 나오면 괄호없이 그냥 결과를 return해준다.

 

 

 

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
N = int(input()) # 1<=N<=64 범위의 2의 제곱수
video = [list(map(int, list(input().strip()))) for _ in range(N)]
result = "" # 결과
def compress(arry): # 2차원 배열을 압축해주는 함수
    global result
    standard = arry[0][0] # 기준점
    for i in range(len(arry)):
        for j in range(len(arry[0])):
            if arry[i][j] != standard: # 다른게 존재하면 사분할
                result += "("
                quad(arry)
                result += ")"
                return None
    result += str(standard)
def quad(arry): # 4분할하는 함수
    n = len(arry)//2
    for i in range(2):
        for j in range(2):
            compress([row[j*n:(j+1)*n] for row in arry[i*n:(i+1)*n]])
compress(video)
print(result)
 

 

 

 

 

 

 

 

 

 해설

 

- 압축을 확인하며 만약 모든 요소가 같으면 하나의 요소로 압축해주는 함수 compress와 다른 요소가 있을 경우

해당 배열을 4분할 해주는 함수 quad를 이용해서 해결했다. global로 변수를 선언하여 분할시에만 괄호를 쳐주고 그 분할된 값으로 다시 compress 한다. 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- input()의 결과물을 list처리하면 \n이 생긴다. strip 작업이 필요하다.

 

- numpy없이 2차원배열을 slicing 하기 위해서는 행을 먼저 slicing 해주고 그 값을 대상으로 다시 slicing한 배열을 만들어주면 된다.(코드 21번째 줄)

 

- 너무 쉬운문제인데 다 풀어놓고 처음에 video 리스트를 2차원이 아닌 3차원으로 받아서 하루동안 고민했다.. 진짜 말도 안되는 실수이다. 입력이 잘못됬다고 의심하지를 않았다..