쿼드트리 이미지 복원

문제 설명

8x8 크기의 이차원 정수 배열이 쿼드트리(Quad-Tree) 알고리즘을 이용해 문자열로 압축되어 주어집니다. 이 문자열을 해석해 원래의 8x8 배열을 복원하려고 합니다.

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

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

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

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

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

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

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

문자열로 주어진 쿼드트리 압축 결과 compressed가 입력으로 주어질 때, 쿼드트리 압축되기 전의 8x8 크기의 이차원 정수 배열을 반환하는 solution 함수를 작성하시오.

제한 사항

• compressed는 항상 8x8 배열을 올바른 쿼드트리 규칙으로 압축한 결과만 주어집니다.

• compressed는 '(', ')', '0', '1' 문자로만 구성되어 있습니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 입력이 "1"이므로 전체 8x8 영역이 모두 1로 채워져 있는 배열로 복원됩니다.

2번 테스트케이스 설명

• 입력 "(((1000)000)000)"은 재귀적으로 분할했을 때 가장 왼쪽 위 영역만 1이고, 나머지 모든 영역이 0으로 복원됩니다.

  • 최상위 8x8을 4개의 4x4 영역으로 나누고

  • 다시 왼쪽 위 4x4를 4개의 2x2로 나누는 식으로 단계적으로 복원하면,

    • 왼쪽 위 2x2 중에서도 가장 왼쪽 위만 1이고 나머지는 0입니다.

  • 나머지 하위 구역은 모두 0으로 채워집니다.

3번 테스트케이스 설명

• 입력 "(1(011(1101))(0111)0)"을 재귀적으로 해석하면,

  • 1: 왼쪽 위 4x4 영역이 모두 1

  • (011(1101)): 오른쪽 위 4x4 영역

  • (0111): 왼쪽 아래 4x4 영역

  • 0: 오른쪽 아래 4x4 영역이 모두 0

• 이 과정을 거쳐서 다음과 같은 8x8 배열로 복원됩니다:

  [
      [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]
  ]