[Baekjoon] 백준 1992 쿼드트리

문제

쿼드트리

주어진 영상이 0으로만 이루어져 있다면 결과는 0이 되고 혹은 그 반대면 결과가 1이 된다.
만약 0과 1이 섞여 있으면 전체를 한번에 나타내지 못하고 4개의 영역으로 나누어 각 영역을 압축한 결과를 차례로 괄호 안에서 묶어서 표현한다.

풀이

분할 정복 알고리즘을 사용하여 해결할 수 있다.
분할 정복은 재귀적으로 큰 문제를 하위 문제로 쪼개어 하위 문제를 해결하고 모아서 상위 문제를 해결하는 방식이다.
2차원 배열을 같은 숫자로 구성된 4등분 단위로 압축 및 재귀적으로 처리하여 괄호로 묶는다. Stack으로도 구현 가능하다.

/*
┌───┬───┐
│ 1 │ 2 │
├───┼───┤
│ 3 │ 4 │
└───┴───┘
*/
let n = Int(readLine()!)!
var graph: [[String]] = []

for _ in 0..<n {
    let row = readLine()!.map { String($0) }
    graph.append(row)
}

// 분할정복 함수 - (y, x) 위치에서 size 크기의 정사각형 영역 처리
func go(_ y: Int, _ x: Int, _ size: Int) -> String {
    let base = graph[y][x]
    var ret = ""

    for row in y..<y+size {
        for col in x..<x+size {
            // 입력 조건이 2^k 이므로 0이하로 들어올 가능성이 없기 때문에 기저 사례 필요 x
            if size == 1 { return graph[y][x] }

            // 하나라도 값이 다르다면 4분할하여 재귀적으로 검사
            if base != graph[row][col] {
                ret += "("
                ret += go(y, x, size/2)
                ret += go(y, x+size/2, size/2)
                ret += go(y+size/2, x, size/2)
                ret += go(y+size/2, x+size/2, size/2)
                ret += ")"
                return ret
            }
        }
    }

    // 모두 같은 값이면 해당 값 반환
    return base
}

// (0, 0)부터 분할정복 시작
print(go(0, 0, n))