9663 swift - N-Queen

https://www.acmicpc.net/problem/9663

[Swift] BackTracking / 백트래킹 / 퇴각검색

 

시간 초과. 얼마나 효율적으로 검사 할 수 있는가. 

시간 초과.

import Foundation


let n=Int(readLine()!)!
var board=Array(repeating: 0, count: n)
var queen=0
var count=0

public func progressTime(_ closure: () -> ()) -> TimeInterval {
	let start = CFAbsoluteTimeGetCurrent()
	closure()
	let diff = CFAbsoluteTimeGetCurrent() - start
	return (diff)
}

print(progressTime {
	dfs(0)
	print(count)
})

func check(_ level: Int) -> Bool {
	for i in stride(from: 0, to: level, by: 1) {
		if board[i] == board[level] || abs(level - i) == abs(board[i] - board[level]) {
			return false
		}
	}
	return true
}

func dfs(_ level: Int) {
	if level == n {
		count += 1
		return
	} 

	for i in 0..<n {
		board[level] = i
		if check(level) {
			dfs(level + 1)
		}
	}
}

 

시간 초과

 

시간 복잡도를 최대한 줄이기 위해서 재귀도 사용하지 않음.

import Foundation


let n=Int(readLine()!)!
var board=Array(repeating: false, count: n)
var diagonal1 = Array(repeating: false, count: 2*n-1)
var diagoanl2 =  Array(repeating: false, count: 2*n-1)
var count=0

public func progressTime(_ closure: () -> ()) -> TimeInterval {
	let start = CFAbsoluteTimeGetCurrent()
	closure()
	let diff = CFAbsoluteTimeGetCurrent() - start
	return (diff)
}

print(progressTime {
	btk(0)
	print(count)
})

func check(_ i:Int, _ k:Int) -> Bool{
	if board[k] || diagonal1[i+k] || diagoanl2[i-k+n-1]{
		return false
	}
	return true
}

func btk(_ row:Int){
	if row == n{
		count += 1
		return
	}
	for i in 0..<n{
		if check(row, i){
			board[i] = true; diagonal1[row+i] = true; diagoanl2[row-i+n-1] = true
			btk(row+1)
			board[i] = false; diagonal1[row+i] = false; diagoanl2[row-i+n-1] = false
		}
	}
}

시간초과 해결