[Swift] 프로그래머스 - N-Queen

문제

자연수 n을 입력받음

n*n 체스판에서 퀸이 서로 공격할 수 없게끔 배치할 수 있는 경우의 수 리턴

접근 방법

dfs에서 모두 돌리지 않고 특정 조건만 돌려주는 백트레킹 접근

퀸은 가로 세로 대각선 공격을 함으로 라인별로 하나씩 배치해주면 가로 체크할 필요가 없으니 라인별로 dfs 돌아주되, 세로, 대각선을 체크하면서 불필요한 부분들 continue로 최적화

대각선의 경우 한 라인씩 전진할 때마다 좌우 shift

코드

	func solution(_ n:Int) -> Int {
	let banList: [Bool] = Array(repeating: false, count: n)
	let leftCheck = Array(repeating: true, count: n)
	let rifhtCheck = Array(repeating: true, count: n)
	let line = Array(repeating: true, count: n)
	var count = 0
	dfs(line, 0, leftCheck, rifhtCheck, banList, -3, n, &count)
	return count
	}
	func dfs(_ line: [Bool], _ depth: Int, _ lc: [Bool], _ rc: [Bool], _ banList: [Bool], _ bf: Int, _ n: Int, _ count: inout Int) {
	if depth == n {
	count += 1
	return
	}
	for i in 0 ..< n {
	if i == bf-1 || banList[i] || i == bf+1 { continue } // 이전에 넣은 값으로 비교
	else if lc[i] && rc[i] { // 대각선
	var line = line
	line[i] = false
	var lc = lc
	var rc = rc
	// 세로 제외요소 추가
	var banList = banList
	banList[i] = true
	// 오른쪽 왼쪽 둘다 좌우로 퍼져야 하니깐 둘다 값 넣어서
	lc[i] = false
	rc[i] = false
	// 왼쪽 shift
	lc.removeFirst()
	lc.append(true)
	// 오른쪽 shift
	rc.removeLast()
	rc.insert(true, at: 0)
	dfs(line, depth+1, lc, rc, banList, i, n, &count)
	}
	}
	}
	for i in 1 ..< 12 {
	print(solution(i))
	}

view raw N-Queen(프로그래머스).swift hosted with ❤ by GitHub