백준 1074 Z

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

분류: 재귀

---

접근방식

백준 1992 쿼드트리 와 비슷한 문제였습니다. 

대신 쿼드트리처럼 전부 방문하면 시간 제한에 걸리게 되기 때문에
어느 사분면에 포함되는지 체크해서 해당 분면만 재귀적으로 호출해줘야 합니다.

방문의 순서는 알고 있기 때문에 해당 사분면에 가능한 방문의 범위도 알 수가 있습니다. 

4x4 배열이라면 각각 0~3, 4~7, 8~11, 12~15 사이의 값이 오겠죠?

이를 이용해서 방문 가능한 카운트 범위도 같이 넘겨주면서 해결했습니다.

 

해결방법

import Foundation

extension Int {
    func pow(_ n: Int) -> Int {
        var powered = 1
        (0..<n).forEach { _ in
            powered *= self
        }
        return powered
    }
}

let nrc = readLine()!.split(separator: " ").map { Int(String($0))! }

func visit(_ rangeRow: CountableRange<Int>, _ rangeCol: CountableRange<Int>, _ visitRange: CountableRange<Int>) {
    guard rangeRow.count != 1 else {
        print(visitRange.startIndex)
        return
    }
    
    let frontRow = rangeRow.startIndex..<(rangeRow.startIndex + rangeRow.endIndex)/2
    let frontCol = rangeCol.startIndex..<(rangeCol.startIndex + rangeCol.endIndex)/2
    let backRow = (rangeRow.startIndex + rangeRow.endIndex)/2..<rangeRow.endIndex
    let backCol = (rangeCol.startIndex + rangeCol.endIndex)/2..<rangeCol.endIndex
    let quardOfVisits = visitRange.count/4
    
    switch (nrc[1], nrc[2]) {
        case (let row, let col) where frontRow ~= row && frontCol ~= col:
             visit(frontRow, frontCol, visitRange.startIndex..<visitRange.startIndex + quardOfVisits)
        case (let row, let col) where frontRow ~= row && backCol ~= col:
            visit(frontRow, backCol, (visitRange.startIndex + quardOfVisits)..<visitRange.startIndex + quardOfVisits*2)
        case (let row, let col) where backRow ~= row && frontCol ~= col:
            visit(backRow, frontCol, (visitRange.startIndex + quardOfVisits*2)..<visitRange.startIndex + quardOfVisits*3)
        case (let row, let col) where backRow ~= row && backCol ~= col:
            visit(backRow, backCol, (visitRange.startIndex + quardOfVisits*3)..<visitRange.startIndex + quardOfVisits*4)
        default:
            break
    }
}

visit(0..<2.pow(nrc[0]), 0..<2.pow(nrc[0]), 0..<2.pow(nrc[0] * 2))

 

 

배운점

쿼드트리 문제를 풀고 온거였음에도... 시간이 한참이나 걸렸다.

화...이...팅....