[Algorithm/BOJ] 1074 - Z (분할정복, 재귀) Swift

문제풀이: 

2^N X 2^N을 2 X 2 까지 분할해서 타겟 좌표를 찾아야 한다.

하지만 N의 범위는 15까지 이기 때문에 일일히 찾으면 2^15 * 2^15 시간 초과가 발생한다. 

그러므로 타겟 좌표에 해당하는 행렬일 때만 탐색하고 아닐 때는 방문한 걸로 치고 넘어가서 시간을 줄여야 한다.

 

코드:

import Foundation

func solution(_ powN: Int, _ nr: Int, _ nc: Int) {
    if nr == r && nc == c {
        print(result)
        return
    }
    
    // 원하는 좌표가 포함되는 행렬이 아닐 때 방문한 걸로 치고 넘어가기 (시간 줄이기)
    if !(nr <= r && r < nr + powN && nc <= c && c < nc + powN) {
        result += powN * powN
        return
    }
    
    // 분할한 각 사분면으로 재귀 호출
    solution(powN / 2, nr, nc)
    solution(powN / 2, nr, nc + powN / 2)
    solution(powN / 2, nr + powN / 2, nc)
    solution(powN / 2, nr + powN / 2, nc + powN / 2)
}

let nrc = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nrc[0]
let r = nrc[1]
let c = nrc[2]
var result = 0
solution(Int(pow(2.0, Double(n))), 0, 0)

 

문제: 

1074번: Z