코딩테스트: 쿼드트리 (백준 1992) + 쿼드트리로 압축 및 해제하는 과정

• https://www.acmicpc.net/problem/1992

문제

예제 2

입력:
4
0011
0011
1000
0100

출력:
(01(1001)0)

코드

let n = Int(readLine()!)!
let a = (0..<n).map { _ in readLine()!.map(String.init) }

func isAllSame(_ y: Int, _ x: Int, _ size: Int) -> String? {
    for i in 0..<size {
        for j in 0..<size {
            if a[y+i][x+j] != a[y][x] {
                return nil
            }
        }
    }
    
    return a[y][x]
}

var result = ""
func recursive(_ y: Int = 0, _ x: Int = 0, _ size: Int = n) {
    if let char = isAllSame(y, x, size) {
        result += char
        return
    }
    
    result += "("
    
    let size = size / 2
    for i in [0, 1] {
        for j in [0, 1] {
            recursive(y + size * i, x + size * j, size)
        }
    }
    
    result += ")"
}

recursive()
print(result)

압축 과정 풀이

해당 코드는 백준 문제 “쿼드트리”를 해결하기 위한 Swift 구현으로, 쿼드트리를 이용한 ‘압축’ 과정에 해당합니다. 문제의 목표는 2차원 이미지 데이터를 압축된 형태로 표현하는 것입니다. 압축은 모든 값이 동일한 부분영역을 하나의 값으로 표현하고, 그렇지 않은 경우 네 개의 작은 영역으로 분할하여 재귀적으로 압축을 시도하는 방식으로 진행됩니다.

1. 입력 처리
   n은 이미지의 크기이며, 이미지 데이터는 a라는 2차원 배열에 저장됩니다.readLine()을 통해 입력을 받아 a 배열에 저장된 후, 각 요소는 문자열로 변환됩니다.
2. 모든 값이 동일한지 확인하는 함수 isAllSame

   isAllSame(y: Int, x: Int, size: Int) -> String?는 현재 영역의 모든 값이 동일한지 확인하는 함수입니다.
   주어진 (y, x) 좌표에서 시작하여 size 크기의 정사각형 영역을 검사합니다.
   만약 모든 값이 동일하다면 해당 값을 반환하고, 그렇지 않으면 nil을 반환합니다.

3. 재귀 함수 recursive

   이 함수는 쿼드트리 방식으로 이미지를 압축합니다.
   현재 영역의 모든 값이 동일한 경우, 그 값을 결과 문자열에 추가하고 종료합니다.
   그렇지 않은 경우, 해당 영역을 네 개의 작은 영역으로 분할하고, 각 영역에 대해 재귀적으로 호출을 합니다.
   영역이 분할되기 전에는 "("를 결과 문자열에 추가하고, 모든 분할이 끝난 후에는 ")"를 추가합니다.

4. 쿼드트리 압축 알고리즘의 실행

   recursive() 함수를 호출하여, 처음에는 전체 이미지를 검사합니다.
   압축된 결과는 result에 저장됩니다.

5. 압축된 문자열 출력 및 후처리

   최종 압축된 문자열 result를 출력합니다.
   추가적으로, 압축된 문자열에서 특정 기호를 변환하여 별도로 가공된 문자열을 출력합니다.
   마지막으로, 압축된 문자열을 해제하여 원래 이미지 형식으로 복원하고 출력합니다.

예제 설명

예를 들어, 다음과 같은 4×4 이미지를 고려해 봅시다:

0 0 0 0
0 0 1 1
0 0 1 1
0 0 1 1

• 이 경우, 왼쪽 상단 2×2 영역, 왼쪽 하단 2×2 영역은 모두 0이기 때문에 0으로 압축됩니다.
• 오른쪽 하단 2×2 영역은 모두 1이기 때문에 1로 압축됩니다.
• 오른쪽 상단 영역은 다시 4 파트로 나눠집니다. 1×1 크기로 나눈 뒤 좌상 시계방향부터 볼 경우 0, 0, 1, 1 이 됩니다.
• 최종 결과는 (0(0011)01)이 됩니다.

중요 포인트

• 재귀 함수에서 isAllSame 함수는 모든 값이 동일한지 확인하는 역할을 합니다.
• 모든 값이 동일하지 않은 경우, 영역을 네 개로 나누어 재귀 호출을 통해 압축을 진행합니다.
• 최종 결과는 압축된 형태의 문자열로 나타나며, 이는 이미지의 효율적인 저장 및 전송을 가능하게 합니다.

해제 과정 풀이

압축을 했다면 해제하는 과정도 있어야 하겠죠? 쿼드트리 압축 문제에서, 압축된 데이터를 원래의 이미지로 복원하는 과정은 중요한 부분입니다. 주어진 코드는 압축된 문자열을 해제하여 원본 이미지를 복원하는 함수 decompressQuadtree를 구현하고 있습니다. 이 해설에서는 이 코드를 자세히 설명하겠습니다.

코드

func decompressQuadtree(compressed: String, size: Int? = nil) -> [[String]] {
    let compressed = compressed.replacingOccurrences(of: ")", with: "")
    let compressedArray = compressed.map(String.init)
    
    let size = size ?? getSize()
    var matrix = Array(repeating: Array(repeating: "0", count: size), count: size)
    
    var stringIndex = 0
    decompress(stringIndex: &stringIndex, size: size)
    
    func decompress(stringIndex: inout Int, row: Int = 0, col: Int = 0, size: Int) {
        let head = compressedArray[stringIndex]
        stringIndex += 1
        
        if head == "0" || head == "1" {
            for i in 0..<size {
                for j in 0..<size {
                    matrix[row + i][col + j] = (head == "1" ? "1" : "0")
                }
            }
        } else {
            let half = size / 2
            decompress(stringIndex: &stringIndex, row: row, col: col, size: half)
            decompress(stringIndex: &stringIndex, row: row, col: col + half, size: half)
            decompress(stringIndex: &stringIndex, row: row + half, col: col, size: half)
            decompress(stringIndex: &stringIndex, row: row + half, col: col + half, size: half)
        }
    }
    
    func getSize() -> Int {
        var stringIndex = 0
        let depth = Double(getDepth(stringIndex: &stringIndex, depth: 0))
        return Int(pow(Double(2), depth))
    }
    
    func getDepth(stringIndex: inout Int, depth: Int) -> Int {
        let head = compressedArray[stringIndex]
        stringIndex += 1
        
        var maxDepth = depth
        if head == "0" || head == "1" {
            return depth
        } else {
            for _ in 0..<4 {
                maxDepth = max(getDepth(stringIndex: &stringIndex, depth: depth + 1), maxDepth)
            }
        }
        
        return maxDepth
    }
    
    return matrix
}

let decompressedString = decompressQuadtree(compressed: compressedString)
    .map { $0.joined(separator: " ") }
    .joined(separator: "\n")
print("decompressed:", decompressedString, separator: "\n")

• 이 코드는 decompressQuadtree 함수를 사용하여 압축된 문자열을 해제하고, 2차원 배열을 문자열 형태로 변환한 후 출력합니다. 각 행은 공백으로 구분되며, 행들은 줄 바꿈으로 구분됩니다.

쿼드트리 해제 함수 설명

쿼드트리 압축에서 각 영역을 “0” 또는 “1”로 표현하거나, 네 개의 하위 영역으로 나누는 방식으로 압축됩니다. 이 코드는 이러한 압축 데이터를 입력으로 받아 원본 이미지를 복원하는 과정입니다.

함수 decompressQuadtree

이 함수는 다음과 같은 작업을 수행합니다:

1. 입력 문자열 처리
   입력된 압축 문자열에서 닫는 괄호 )를 제거하여 compressed 문자열을 생성합니다.
   이후, compressedArray라는 배열로 변환하여 문자열의 각 문자를 개별 요소로 저장합니다.
2. 크기 초기화
   이미지의 크기는 size 매개변수로 제공될 수 있으며, 제공되지 않을 경우 getSize() 함수를 호출하여 자동으로 계산합니다.
   이미지의 크기와 동일한 2차원 배열 matrix를 생성하여 초기값을 "0"으로 설정합니다.
3. 해제 과정
   decompress 함수를 호출하여 압축된 데이터를 원본 이미지로 복원합니다. 이 함수는 재귀적으로 압축된 데이터에서 정보를 읽어와 matrix를 채웁니다.

함수 decompress

1. 이 함수는 재귀적으로 호출되어 압축 데이터를 해제합니다:
2. 단일 값 처리
   만약 현재 처리 중인 문자가 "0" 또는 "1"인 경우, 현재 영역의 모든 값을 해당 문자로 설정합니다. 이는 해당 영역이 단일 색상으로 채워져 있음을 의미합니다.
3. 쿼드트리 분할
   현재 문자가 "("인 경우, 네 개의 하위 영역으로 분할하여 각 영역에 대해 decompress 함수를 재귀적으로 호출합니다. 이때, 각 하위 영역은 현재 영역의 절반 크기로 설정됩니다.

함수 getSize 및 getDepth

• getSize
  압축 문자열의 깊이를 계산하여 이미지의 크기를 결정합니다. getDepth 함수를 호출하여 쿼드트리의 최대 깊이를 계산하고, 이 깊이에 따라 이미지의 크기를 2의 거듭제곱으로 결정합니다.
• getDepth
  재귀적으로 호출되어 쿼드트리의 깊이를 계산합니다. 현재 노드가 "0" 또는 "1"인 경우 깊이를 반환하고, 그렇지 않은 경우 네 개의 하위 영역을 확인하여 최대 깊이를 계산합니다.

실행 예제

 🤖 이 포스트는 ChatGPT-4o 등의 생성형 AI의 도움을 받아 작성되었습니다. 🤖