백준 1992 쿼드트리

출처: https://www.acmicpc.net/problem/1992

분류: 재귀

---

접근방식

사각형의 영역을 1, 2, 3, 4분면씩 쪼개서 재귀로 풀 수 있는 문제였습니다.

고민하다가 잘 모르겠어서 다른 분들 풀이를 참고해서 풀었네요 ㅠ-ㅠ

처음엔 포문을 먼저 돌려서 모두 1인지 0인지 체크하는 방식으로 풀었는데, 

다른 분들의 풀이를 보니 어차피 재귀로 돌릴거라면 먼저 체크하지 않아도 결과를 가지고 확인해서 풀 수도 있네요!

 

해결방법

처음 풀이 포문으로 전부 0인지 1인지 체크, 아니라면 compression

func compress(size: Int, at point: Point) -> String {
    guard size != 1 else {
        return String(map[point.r][point.c])
    }

    var onlyZero = true
    var onlyOne = true
    for r in point.r..<point.r+size {
        for c in point.c..<point.c+size {
            if map[r][c] == 1 {
                onlyZero = false
            } else {
                onlyOne = false
            }
        }
    }

    if onlyOne {
        return "1"
    } else if onlyZero {
        return "0"
    } else {
        var result = "("
        result += compress(size: size/2, at: point)
        result += compress(size: size/2, at: Point(point.r, point.c + size/2))
        result += compress(size: size/2, at: Point(point.r + size/2, point.c))
        result += compress(size: size/2, at: Point(point.r + size/2, point.c + size/2))
        result += ")"
        return result
    }
}

print(compress(size: n, at: Point(0, 0)))

 

다른 분의 참고해서 똑똑이 처럼 풀어봤습니다.. 저도 열심히 해서 이렇게 깔끔하게 풀 수 있게 되길...

import Foundation

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

typealias Point = (r: Int, c: Int)

func compress(_ rangeRow: CountableRange<Int>, _ rangeCol: CountableRange<Int>) -> String {
    guard rangeRow.count != 1 else {
        return String(map[rangeRow.startIndex][rangeCol.startIndex])
    }
    
    let startRow = rangeRow.startIndex..<(rangeRow.startIndex + rangeRow.endIndex)/2
    let endRow = (rangeRow.startIndex + rangeRow.endIndex)/2..<rangeRow.endIndex
    let startCol = rangeCol.startIndex..<(rangeCol.startIndex + rangeCol.endIndex)/2
    let endCol = (rangeCol.startIndex + rangeCol.endIndex)/2..<rangeCol.endIndex
    
    let video1 = compress(startRow, startCol)
    let video2 = compress(startRow, endCol)
    let video3 = compress(endRow, startCol)
    let video4 = compress(endRow, endCol)
    
    switch (video1, video2, video3, video4) {
        case ("0", "0", "0", "0"): return "0"
        case ("1", "1", "1", "1"): return "1"
        default: return "(\(video1)\(video2)\(video3)\(video4))"
    }
}

print(compress(0..<n, 0..<n))

 

배운점

재귀로 풀 수 있을 것 같았는데 풀이까지 가질 못했다.. 

재귀는 너무 어렵게 생각하지말고 기저 사례부터 생각해서 차근차근..!