백준 9663번 N-Queen

정답 : 

let n = Int(readLine()!)!
var issue1 = Array(repeating: false, count: n) // column을 차지하고 있는지
var issue2 = Array(repeating: false, count: 2 * n - 1) // / 방향 대각선을 차지하고 있는지
var issue3 = Array(repeating: false, count: 2 * n - 1) // \ 방향 대각선을 차지하고 있는지
var cnt = 0
func check(num : Int) { // cur번째 row에 말을 배치할 예정임
    if num == n { // N개를 놓는데 성공했다면
        cnt += 1
        return
    }
    for i in 0..<n { // (cur, i)에 퀸을 놓을 예정
        if issue1[i] || issue2[i + num] || issue3[num - i + n - 1] { // column이나 대각선 중에 문제가 있다면
            continue
        }
        issue1[i] = true
        issue2[i+num] = true
        issue3[num-i+n-1] = true
        check(num: num + 1)
        issue1[i] = false
        issue2[i+num] = false
        issue3[num-i+n-1] = false
    }
}
check(num: 0)
print(cnt)

해당 문제는 그 자리에 놓여 있는 경우를 true로 잡고 진행한다.

 

따라서 / 방향 대각선이나, \ 방향 대각선에도 true가 있다면 놓을수 없으니 넘어간다.

 

골드 문제라 그런지 너무 어려운 것 같다.