[Algorithm] 백준 - 9663번 N-Queen (Swift)

문제 소개

https://www.acmicpc.net/problem/9663
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 유명한 문제이다.
 

문제 풀이

유명한 문제여서 아주 유명한 풀이가 있다. 이 문제는 사실 어렵지는 않지만 시간복잡도를 최대한 줄이는 것이 관건이라고 할 수 있겠다. 가장 유명한 풀이는 아래와 같다. 한 줄에 무조건 퀸 하나가 들어가야 하기 때문에 한줄한줄 넘어가면서 퀸을 놓는 방식이다. 그리고 colums라는 배열에 쌓아준다.
 
그리고 퀸을 놓을 때 같은 줄에 있는지, 대각선이라면 x, y 좌표의 차이가 같을 경우인지를 판별한 뒤 넣는다.

import Foundation

let n = Int(readLine()!)!
var colums = Array(repeating: -1, count: n)
var count = 0

func solution(_ depth: Int) {
    if depth == n {
        count += 1
        return
    }
    
    for j in 1...n {
        colums[depth] = j
        if check(depth) {
            solution(depth+1)
        }
    }
}

func check(_ i: Int) -> Bool {
    for k in 0..<i {
        if colums[i] == colums[k] || abs(colums[i] - colums[k]) == abs(i-k) {
            return false
        }
    }
    
    return true
}

solution(0)
print(count)

 
 

문제점

문제점은 시간이었다. 12가 넘어가는 순간 시간이 오래 걸려 백준에서는 시간초과가 났다.

 
check 함수가 문제였다. 모든 경우를 확인하기 때문에 좀 더 빠른 판별볍이 필요했다. 그래서 생각한 아이디어는 다음과 같다.

대각선의 경우 합과 차이가 일정하게 된다. 따라서 합과 차이를 통해 대각선을 판별하게 하였다. 차이의 경우 마이너스가 될 수 있으므로 n을 더해서 0 이상의 수로 유지했다.

import Foundation

let n = Int(readLine()!)!
var columns = Array(repeating: -1, count: n)
var count = 0
var visited = Array(repeating: false, count: n)
var visited1 = Array(repeating: false, count: 2 * n) // \ 대각선 부분
var visited2 = Array(repeating: false, count: 2 * n) // / 대각선 부분

func solution(_ depth: Int) {
    if depth == n {
        count += 1
        return
    }
    
    for j in 0..<n {
        if !visited[j] && !visited1[depth + j] && !visited2[depth - j + n] {
            columns[depth] = j
            visited[j] = true
            visited1[depth + j] = true
            visited2[depth - j + n] = true
            solution(depth + 1)
            visited[j] = false
            visited1[depth + j] = false
            visited2[depth - j + n] = false
        }
    }
}

solution(0)
print(count)

 
결과는 아래와 같았다. 약 6초 정도의 시간으로 가까스로 통과했다.