쿼드트리

1. 조건

• N : 영상의 크기 ( 1 <= N <= 64 인 2의 제곱수 )
• arr : N x N 행열 ( 0과 1로 이뤄진 N개의 문자열이 N번 들어옴 )

2. 출력

• 모두 0이면 0으로 압축 / 모두 1이면 1로 압축한다.
• 4부분으로 나누어 영상을 압축한 결과를 출력한다.

INPUT

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

OUTPUT

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

3. 방식

• 나눈 부분의 숫자가 같은지 확인한다.
• 같다면 압축하고 다르면 1 X 1이 될 때까지 나누어 다시 체크한다
• 한번씩 나눌 때마다 괄호가 생긴다.
  

4. 코드

# 쿼드트리


def Check(r, c, n):  # 같은지 비교하는 함수
    global ans  # 결과를 글로벌로 지정

    point = arr[r][c]  # 행열의 처음 값을 비교 값으로 설정
    error = 0  # 행열의 값이 다른 경우를 찾기 위한 플래그 변수
    half = n // 2  # n의 절반 값

    if n > 1:  # n이 1보다 큰 경우
        for i in range(n):  # 행열의 값이 같은지 확인
            for j in range(n):
                if arr[r + i][c + j] != point:
                    error = 1  # 다른 경우 에러를 표시하고 반복을 빠져나옴
                    break
        if not error:  # 행열의 값이 같은 경우
            ans += str(point)  # 값 추가
        else:  # 같지 않은 경우
            ans += "("  # 4부분으로 나누기 전 괄호 설정
            Check(r, c, half)  # 재귀
            Check(r, c + half, half)
            Check(r + half, c, half)
            Check(r + half, c + half, half)
            ans += ")"

    else:  # n이 1인 경우
        ans += str(point)  # 해당 값을 더함


N = int(input())  # 영상의 크기
arr = [list(map(int, input())) for _ in range(N)]  # 문자열을 2차원 int 리스트로 저장
ans = ""

Check(0, 0, N)
print(ans)

문자열을 2차원 배열로 바꾸는 코드

arr = [list(map(int, input())) for _ in range(N)]