문제 링크 (opens new window)

문제

• 백트래킹 중에 edge 케이스 도달 시 exit으로 프로그램 종료해버리기
• horizon으로 놓은 가로선들 0개부터 3개까지 체크
• 재귀호출시 3개 중에 추가할 사다리 갯수 중 하나 제외한 갯수를 전달

import Foundation

let nmh = readLine()!.split(separator: " ").map { Int($0)! }; let n = nmh[0]; let m = nmh[1]; let h = nmh[2]
var visited: [[Int]] = .init(repeating: .init(repeating: 0, count: 11), count: 31)
var ret = 4

// visited는 놓인 사다리 가로선
func check() -> Bool {
    for i in 1...n {
        var start = i
        for j in 1...h {
            // 가로선이 놓여있으면 이동
            if visited[j][start] == 1 {
                start += 1
            } else if visited[j][start - 1] == 1 {
                start -= 1
            }
        }

        if start != i { return false }
    }
    return true
}

func go(_ y: Int, _ cnt: Int) {
    if cnt == 0 {
        for i in 1...n {
            var start = i
            for j in 1...h {
                // 가로선이 놓여있으면 이동
                if visited[j][start] == 1 {
                    start += 1
                } else if visited[j][start - 1] == 1 {
                    start -= 1
                }
            }

            if start != i { return }
        }
        print(ret)
        exit(0)
    }

    for i in y...h {
        for j in 1..<n {
            if visited[i][j] == 1 || visited[i][j-1] == 1 || visited[i][j+1] == 1 { continue }
            visited[i][j] = 1
            go(i, cnt - 1)
            visited[i][j] = 0
        }
    }
}

for _ in 0..<m {
    let ab = readLine()!.split(separator: " ").map { Int($0)! }
    visited[ab[0]][ab[1]] = 1
}

var horizon = 0
while(horizon <= 3) {
    ret = horizon
    go(1, horizon)
    horizon += 1
}
print(-1)