쿼드트리 이미지 압축

문제 설명

8x8 크기의 이차원 정수 배열 img가 주어집니다. 배열의 각 원소는 0 또는 1로만 이루어져 있습니다. 이 배열을 쿼드트리(Quad-Tree) 알고리즘을 이용하여 문자열로 압축하려고 합니다.

쿼드트리 알고리즘을 이용한 압축 과정은 다음과 같습니다.

1. 현재 구역이 모두 0으로만 이루어져 있거나 모두 1로만 이루어져 있으면, 해당 값('0' 또는 '1')을 그대로 문자열로 반환합니다.

2. 그렇지 않은 경우, 해당 구역을 4개의 동일한 크기의 하위 구역으로 나눕니다.

   • 하위 구역의 순서는 왼쪽 위 → 오른쪽 위 → 왼쪽 아래 → 오른쪽 아래입니다.

   • 각 하위 구역에 대해 같은 방식으로 재귀적으로 압축을 수행합니다.

3. 분할한 4개의 하위 구역에서 얻은 압축 결과를 차례대로 이어 붙인 뒤, 전체를 소괄호로 감싸 '(XXXX)' 형태의 문자열로 반환합니다.

   • 여기서 X는 각 하위 구역의 압축 결과입니다.

이차원 정수 배열 img이 주어졌을 때, 쿼드트리 알고리즘을 이용하여 압축한 문자열을 반환하는 solution 함수를 작성하시오.

예를 들어,

• 모든 원소가 1인 경우 "1"로 압축되고, 모든 원소가 0인 경우 "0"으로 압축됩니다.

• 예시 1 :

  [
    [1,1,1,1,1,1,1,1],
    [1,1,1,1,1,1,1,1],
    [1,1,1,1,1,1,1,1],
    [1,1,1,1,1,1,1,1],
    [1,1,1,1,1,1,1,1],
    [1,1,1,1,1,1,1,1],
    [1,1,1,1,1,1,1,1],
    [1,1,1,1,1,1,1,1]
  ]
  

  • 이 배열은 모든 원소가 1로 같으므로 결과는 "1"이 됩니다.

• 예시 2 :

  [
    [1,1,1,1,0,0,1,1],
    [1,1,1,1,0,0,1,1],
    [1,1,1,1,1,1,1,1],
    [1,1,1,1,1,1,0,1],
    [0,0,1,1,0,0,0,0],
    [0,0,1,1,0,0,0,0],
    [1,1,1,1,0,0,0,0],
    [1,1,1,1,0,0,0,0]
  ]
  

  • 이 경우에는 구역 내에 서로 다른 값이 섞여 있어 4개의 동일한 크기로 분할한 뒤, 각 하위 구역을 재귀적으로 압축합니다.

  • 최종적으로 "(1(011(1101))(0111)0)"과 같은 형태로 압축됩니다.

제한 사항

• img의 크기는 항상 8x8입니다.

• img의 각 원소는 0 또는 1입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 모든 8x8 배열의 원소가 1이므로 압축 결과는 "1"입니다.

2번 테스트케이스 설명

• 좌상단에 1이 하나 있고 나머지 원소는 모두 0입니다.

  • 먼저 4x4 영역으로 분할한 뒤 쿼드트리 알고리즘을 수행하면 아래와 같습니다:

    • 왼쪽 위 4x4 영역을 다시 4등분하면, 왼쪽 위 2x2 영역은 "1"과 "0"이 섞여 있어 (1000)으로 압축되고, 나머지 세 영역은 모두 "0"으로 압축됩니다.

    • 따라서 4x4 영역 전체는 ((1000)000)이 됩니다.

  • 그 외 나머지 영역은 모두 0이므로 각각 "0"으로 압축됩니다.

• 최종적으로 압축 결과는 "(((1000)000)000)"입니다.

3번 테스트케이스 설명

• 주어진 8x8 배열을 쿼드트리 알고리즘에 따라 재귀적으로 분할하고 압축하면, 결과는 "(1(011(1101))(0111)0)"가 됩니다.