1️⃣ 문제
백트래킹 대표 문제로 유명한 N-Queen 문제를 풀어보았다! 유투브에 외국인 아저씨들도 많이 설명하실 정도로 워낙 유명한 문제니 한번 쯤 푸는 거 추천합니당
2️⃣ 풀이 방법 및 코드
1️⃣ 처음 풀이한 코드
대각선 왼쪽, 오른쪽을 나눠서 각자 계산하고 [[Bool]] 2차원 배열을 검사하다 보니 시간복잡도가 크게 나와 n=12일 때 시간초과가 난다.
import Foundation
func placeQueens(n: Int, depth: Int, checked: [[Bool]], answer: inout Int) {
if depth == n { // 마지막 퀸까지 다 놓았을 때
answer += 1
return
}
for i in 0..<n {
// 현재 행에 퀸을 놓을 수 있는지 확인
if canPutQueen(x: i, y: depth, checked: checked) {
var newChecked = checked
newChecked[depth][i] = true
// dfs
placeQueens(n: n, depth: depth+1, checked: newChecked, answer: &answer)
}
}
}
func canPutQueen(x: Int, y: Int, checked: [[Bool]]) -> Bool {
for i in 0..<checked.count {
// 세로 확인
if checked[i][x] {
return false
// 대각선 왼쪽 확인
} else if 0..<checked.count ~= x-abs(y-i) && checked[i][x-abs(y-i)] {
return false
// 대각선 오른쪽 확인
} else if 0..<checked.count ~= x+abs(y-i) && checked[i][x+abs(y-i)] {
return false
}
}
return true
}
func solution(_ n:Int) -> Int {
var answer = 0
var checked = Array(repeating: [Bool](repeating: false, count: n), count: n)
placeQueens(n: n, depth: 0, checked: checked, answer: &answer)
return answer
}
2️⃣ 개선하여 맞춘 코드
여기서 필요한 가정은 “한 행에는 무조건 하나의 퀸만 있을 수 있다”이다.
그렇다면 checked 2차원 배열이 아니라,
checked[i] = i번째 퀸(=i번째 행에 있는 퀸)의 열 위치
로 하면 1차원 배열만으로도 퀸의 위치를 저장할 수 있음!
import Foundation
func placeQueens(n: Int, depth: Int, checked: [Int], answer: inout Int) {
if depth == n { // 마지막 퀸까지 다 놓았을 때
answer += 1
return
}
for i in 0..<n {
// 현재 행에 퀸을 놓을 수 있는지 확인
if canPutQueen(x: depth, y: i, checked: checked) {
var newChecked = checked
newChecked[depth] = i
// dfs
placeQueens(n: n, depth: depth+1, checked: newChecked, answer: &answer)
}
}
}
func canPutQueen(x: Int, y: Int, checked: [Int]) -> Bool {
// abs를 이용하기 때문에 0~x-1까지
for i in 0..<x {
if checked[i] == y || // 열 체크
abs(x-i) == abs(y-checked[i]) { // 대각선 체크
return false
}
}
return true
}
func solution(_ n:Int) -> Int {
var answer = 0
var checked = [Int](repeating: -1, count: n)
placeQueens(n: n, depth: 0, checked: checked, answer: &answer)
return answer
}
3️⃣ 이 문제를 풀면서 되새긴 점
1️⃣ ~= 연산자
정답 코드에는 없지만 서치하면서 처음으로 알게 된 swift 범위 연산자!
대상이 특정 범위에 속하는지 범위를 체크하는 연산자이다.
(조건문 길이를 줄일 수 있어 아주 굿굿)
if 0..<10 ~= n // 숫자 범위
if "a"..."z" ~= str // 문자열 범위