psychology50 / algorithm-strategies Goto Github PK

func check(_ x: Int, _ y: Int, _ size: Int) {
    if size >= 2 {
        let halfSize = size / 2
        
        if x >= halfSize {
            if y >= halfSize { // 4 분면
                cnt += (size * size) * 3 / 4
                check(x - halfSize, y - halfSize, halfSize)
            } else { // 3 분면
                cnt += (size * size) * 2 / 4
                check(x - halfSize, y, halfSize)
            }
        } else {
            if y >= halfSize { // 1 분면
                cnt += (size * size) * 1 / 4
                check(x, y - halfSize, halfSize)
            } else { // 2 분면
                check(x, y, halfSize)
            }
        }
    }
}

func check(_ x: Int, _ y: Int, _ size: Int) {
    if size < 2 {
        return
    }
    
    let halfSize = size >> 1  // size를 2로 나눔
    let halfSizeSquared = halfSize * halfSize
    
    let xInLowerHalf = x >= halfSize
    let yInLowerHalf = y >= halfSize
    
    if xInLowerHalf && yInLowerHalf { // 4 사분면
        cnt += halfSizeSquared * 3
        check(x - halfSize, y - halfSize, halfSize)
    } else if xInLowerHalf { // 3 사분면
        cnt += halfSizeSquared * 2
        check(x - halfSize, y, halfSize)
    } else if yInLowerHalf { // 1 사분면
        cnt += halfSizeSquared
        check(x, y - halfSize, halfSize)
    } else { // 2 사분면
        check(x, y, halfSize)
    }
}

let N = Int(readLine()!)!
var paper: [[Int]] = []

for _ in 0..<N {
    let line = readLine()!.split(separator: " ").map { Int($0)! }
    paper.append(line)
}

// 카운트 변수명
var whiteCount = 0
var blueCount = 0

// 상수
let WHITE = 0
let BLUE = 1

func divide(_ x: Int, _ y: Int, _ size: Int){
    if check(x, y, size){
        if arr[x][y] == 0{
            white += 1
        }
        else {
            blue += 1
        }
    }
    else {
        let sx = [ x, x, x + size/2, x + size/2 ]
        let sy = [y, y + size/2, y, y + size/2 ]
        
        for i in 0..<4{
            divide(sx[i], sy[i], size/2)
        }
    }
}

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

func divideAndConquer(_ y: Int, _ x: Int, _ size: Int) {
    if isSingleColor(x, y, size) {
        let color = paper[x][y]
        color == WHITE ? (whiteCount += 1) : (blueCount += 1)
    } else {
        let halfSize = size / 2
        let nextCoords = [(y, x), (y + halfSize, x), (y, x + halfSize), (y + halfSize, x + halfSize)]

        for (ny, nx) in nextCoords {
            divideAndConquer(ny, nx, halfSize)
        }
    }
}

func isSingleColor(_ x: Int, _ y: Int, _ size: Int) -> Bool {
    let color = paper[x][y]

    for i in x..<x + size {
        for j in y..<y + size {
            if paper[i][j] != color {
                return false
            }
        }
    }

    return true
}

divideAndConquer(0, 0, N)
print(whiteCount)
print(blueCount)