문제 설명
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
입출력 예 설명
예제 입력#1
8
예제 출력#1
92
예제 입력#2
4 2
문제 풀이
처음에는 column, dig1, dig2 를 set으로 설정해주고 false, true 대신에 insert, remove를 해주었고 contain을 활용하여 풀었다.
하지만 시간초과… remove와 contain은 O(n)을 가질텐데 이를 O(1)로 줄여주기 위해서 배열을 선택해야만 했다…..ㅜ
비트연산자로 이용해서 진짜 개빠르게 푸신 분 있던데 몬지도 모르겠다 ^__^
- Queen 특성상 한 줄에는 하나의 Queen 만 존재 할 수 있다.
- 즉 하나의 row에는 하나의 Queen 만 존재 할 수 있으므로 row의 Queen 증명은 불필요하다.
0..<N - row에서 가능한 col을 결정하기 위해서는 3가지의 증명이 필요하다. 다른 퀸과 겹치는 col은 없는지, 두개의 대각선 방향에서 겹치는 Queen은 없는지
- col 증명은 쉬우니 패스, 대각선은 각각 규칙이 존재한다.
/방향의 대각선은row + col값이 모두 동일하며,\방향의 대각선은row - col값이 모두 동일함을 이용한다.
let N = Int(readLine()!)!
var answer = 0
var column = Array(repeating: false, count: N)
var dig1 = Array(repeating: false, count: 2 * N)
var dig2 = Array(repeating: false, count: 2 * N)
func dfs(_ row: Int = 0) {
if row == N {
answer += 1
return
}
for c in 0..<N {
if column[c] || dig1[c+row] || dig2[c-row+N] { continue }
column[c] = true ; dig1[c+row] = true ; dig2[c-row+N] = true
dfs(row + 1)
column[c] = false ; dig1[c+row] = false ; dig2[c-row+N] = false
}
}
dfs()
print(answer)