[Swift 알고리즘] 백준 1992 쿼드트리

안녕하세요 코코종입니다.

아직 완전탐색쪽을 풀고있는데요! 오늘은 간만에 한방에 맞아서 기분이가 아주 좋답니다 크크

//
//  main.swift
//  BackJoon
//
//  Created by kokojong on 2023/04/16.
//

import Foundation
// 1992 쿼드트리 완탐 실1

// 재귀로 해야할듯 -> 처음에 전체 크기에 대해서 같은지 판단 -> 안되면 ()를 붙이고 다시 1/4씩 나눈다. 반복?

var n = Int(readLine()!) ?? 0
var board: [[Int]] = []
var answer = ""
for _ in 0..<n {
    board.append(Array(readLine()!.map{ Int(String($0))! }))
}

func checkQuad(r: Int, c: Int, k: Int) -> Bool {
    let value = board[r][c] // 처음 값
    
    for i in r..<r+k {
        for j in c..<c+k {
            if board[i][j] != value {
                return false
            }
        }
    }
    return true
}

func quad(r: Int, c: Int, k: Int) { // [r][c] 에서 시작해서 크기가 k
    let value = board[r][c] // 처음 값
    if k == 1 {
        answer += "\(value)"
        return
    }
    
    if checkQuad(r: r, c: c, k: k) {
        answer += "\(value)"
    } else {
        answer += "("
        quad(r: r, c: c, k: k/2)
        quad(r: r, c: c + k/2, k: k/2)
        quad(r: r + k/2, c: c, k: k/2)
        quad(r: r + k/2, c: c + k/2, k: k/2)
        answer += ")"
    }
}

quad(r: 0, c: 0, k: n)
print(answer)

 

아이디어는 간단합니다. 처음에 n의 크기로 주어진 것에서 1. n*n 만큼이 다 같은것인지 확인 2. 다르다면 4부분으로 나눠서 또 확인 3. 같다면 같은 숫자로 통일해서 정답에 추가

이런 흐름으로 했답니다! 아 그리고 괄호를 열고 닫는 부분이 처음에는 헷갈렸는데 4부분으로 나눌때 시작하고 그게 끝나면 닫더라구요!

그대로 코드로 구현했더니 맞았습니당 >< 참고로 문제에서 동일한 행에서 열을 바꿔주는게 먼저라서 quad()를 4개로 나눈 순서도 중요합니다! 확인해보세요