BOJ 1992 쿼드트리

1. 문제 링크: https://www.acmicpc.net/problem/1992

2. 문제 요약: 흑백 영상 압축에 사용되는 쿼드트리를 만들어 보자! 쿼드트리는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 재귀적으로 정의된다.

3. 문제에 얽힌 이야기: 종만북에서 쿼드트리 뒤집기 문제가 쉽길래 도전했으나, 복호화된 쿼드트리 정보를 이용하는 것이 아니라 쿼드트리 자체를 복호화하는 문제여서 삽질을 했다.

4. 문제 접근법: 쿼드트리는 정의 자체가 재귀적으로 이루어져 있으므로, 재귀를 사용한다.

5. 고려할 부분: 2차원 데이터를 4방향으로 나누고, 이를 비교해야 하므로 적절한 데이터형을 골라야 하고, 나누는 방법을 잘 생각해야 한다.


아래는 Swift(4.2) 코드

import Foundation

let n = Int(readLine()!)!
var tree = [String]()
for _ in 0..<n
{
    tree.append(readLine()!)
    
}

func encoding(subTree:[String], N:Int) -> String {
    var str = String()
    
    let zeroStr = String(repeating: "0", count: subTree.count)
    let oneStr = String(repeating: "1", count: subTree.count)
    
    let zeroSubTree = [String](repeating: zeroStr, count: subTree.count)
    let oneSubTree = [String](repeating: oneStr, count: subTree.count)
    
    var leftTop = [String]()
    var rightTop = [String]()
    var leftBottom = [String]()
    var rightBottom = [String]()
    
    if subTree == zeroSubTree
    {
        str += "0"
    }
    else if subTree == oneSubTree
    {
        str += "1"
    }
    else
    {
        for i in 0..<(N/2)
        {
            leftTop.append(String(subTree[i].prefix(N / 2)))
            rightTop.append(String(subTree[i].suffix(N / 2)))
        }
        
        for i in (N/2)..<N
        {
            leftBottom.append(String(subTree[i].prefix(N / 2)))
            rightBottom.append(String(subTree[i].suffix(N / 2)))
        }
        
        str = "(" + encoding(subTree: leftTop, N: N / 2) + encoding(subTree: rightTop, N: N / 2) + encoding(subTree: leftBottom, N: N / 2) + encoding(subTree: rightBottom, N: N / 2) + ")"
    }
    
    return str
}

print(encoding(subTree: tree, N: n))