[Swift] 백준 1992번 쿼드트리

링크: https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

 

백준 2603번 색종의 만들기의 코드에서 파생되었습니다. 풀이: https://gogo-ios.tistory.com/157

색종이 만들기와 다른 점은 0과 1의 갯수를 세는 것이 아닌 String 타입의 결과에 0, 1, 괄호를 추가하는 것입니다.

 

 

이 문제의 풀이는 핵심 풀이는 '모두 같은 숫자가 아니라면 1/4씩 쪼개 4번을 더 탐색한다.' 입니다.

 

1. 전부 같은 숫자인 경우

0 또는 1을 result에 덧붙입니다.

 

2. 전부 같은 숫자가 아닌 경우

result에 열린 괄호를 붙입니다.

1/4씩 쪼개 4번의 탐색을 진행합니다.

탐색이 끝나면 result에 닫힌 괄호를 붙입니다.

 

isSameNumber 함수의 경우 reduce로도 계산이 가능하지만 성능 향상을 기대하기 위해 for문으로 작성하였습니다.

import Foundation

let N = Int(readLine()!)!

var array = [[Int]]()
var result = ""

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

func isSameNumber(_ array: [[Int]]) -> Bool {
    let first = array.first!.first
    
    for i in array {
        for j in i {
            if j != first { return false }
        }
    }
    
    return true
}

func addZeroOrOne(_ array: [[Int]]) {
    if !array.isEmpty {
        if array.first!.first == 0 {
            result.append("0")
        } else {
            result.append("1")
        }
    }
}

func divide(_ array: [[Int]]) {
    if array.count == 1 { // 1. 전부 같은 숫자인 경우
        addZeroOrOne(array)
    } else {
        if !isSameNumber(array) { // 2. 전부 같은 숫자가 아닌 경우
            let half = array.count / 2
            
            // 4분의 1로 나누기
            result.append("(")
            divide(array[0..<half].map { $0[0..<half].compactMap { $0 }})
            divide(array[0..<half].map { $0[half..<array.count].compactMap { $0 }})
            divide(array[half..<array.count].map { $0[0..<half].compactMap { $0 }})
            divide(array[half..<array.count].map { $0[half..<array.count].compactMap { $0 }})
            result.append(")")
        } else { // 1. 전부 같은 숫자인 경우
            addZeroOrOne(array)
        }
    }
}

divide(array)

print(result)