[Swift] 백준 1922 쿼드트리

import Foundation

/// 주어진 영상이 모두 0으로만 되어있으면 압축 결과는 "0"
/// 모두 1로만 되어있으면 압축결과는 "1"
/// 만약 0과 1이 섞여있으면 전체를 한번에 나타내지 못하고
/// 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 이렇게 4개의 영상으로 나누어 압축하게된다.
/// 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다.

/// 분할정복이란? 문제를 나눌 수 없을 때까지 나누어서 다시 합병하여 문제의 답을 얻는 알고리즘
/// 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구함

let N = Int(readLine()!)!

var board = [[Int]]()

for _ in 0..<N {
    let numArr = readLine()!.map { Int(String($0))! }
    board.append(numArr)
}

var result = ""

func check(_ x: Int, _ y: Int, _ n: Int) -> Bool {
    for i in x..<x+n {
        for j in y..<y+n {
            if board[x][y] != board[i][j] {
                return false
            }
        }
    }
    return true
}

func quadTree(_ x: Int, _ y: Int, _ n: Int) {
    if check(x, y, n) {
        result += "\(board[x][y])"
        return
    }
    let w = n / 2
    result += "("
    for i in 0..<2 {
        for j in 0..<2 {
            quadTree(x + i * w, y + j * w, w)
        }
    }
    result += ")"
}

quadTree(0, 0, N)
print(result)