BOJ-9663 N-Queen Swift

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

내가 푼 풀이

- 첫번째 고안한방법은 이차원 배열의 보드를 만들어 전부 순회하며 가능한 모든 경우의수를 구하려했다.

- 이는 O(n^n) 이나 걸리는 너무나 느린 알고리즘이였고, 역시나 시간초과가 떴다.

- 시간을 줄이는 방법을 모르겠어서, 다른 풀이를 참고해보니 이 문제는 백트래킹 문제였다.

- 또한 배열도 이차원 배열이 아닌 일차원 배열로도 풀 수 있다는걸 몰랐다.

 

-> 퀸의 공격범위 특성상 주어진 체스판에 같은 행에 퀸 두개 이상을 배치할 수 없다.

-> 우리는 배치된 퀸의 열과 대각선 방향만 확인하면 된다.

-> 여기서 일차원배열은 board[a] = b 라 하면 이는 a행 b열에 퀸을 배치한다. 라고 의미한다.

-> 같은 행에 두개이상 배치할 수 없기 때문에 1행부터 N행까지 순회하고, 각각 열마다 퀸을 배치해본다..

-> 퀸을 배치하고, 다음 행의 퀸을 배치할 수 있는 범위가 있는지 파악하고, 배치가 가능하다면 퀸을 배치하고 다음 행으로 이동한다.

-> 퀸을 배치할 범위가 존재하지 않다면 다시 돌아와 다른 배치가능한 곳에 배치한다.

-> 이렇게 퀸을 N개만큼 배치했다면 경우의 수 1을 올린다.

-> 여기서 배열 인덱스 특성상 두 원소 (x1, y1), (x2, y2)가 있을때, |x1- x2| == |y1-y2| 가 성립한다면 두 원소는 대각선 위치에 인접해있다고 한다.

0,0	0,1	0,2
1,0	1,1	1,2
2,0	2,1	2,2

배열에서 (1,1) 과 (0,2) 는 |1 - 0| == |1-2| 가 성립하므로 두 원소는 대각선 위치에 있다고 할 수 있다.

위 특성을 이용하여 퀸을 배치한다면 배치한 퀸의 대각선의 위치도 알 수 있게 된다.

 

import Foundation
// 입력받기
let N = Int(readLine()!)!
var arr = Array(repeating: -1, count: N)
var visited = Array(repeating: false, count: N)
var result = 0

// 범위 확인
func checkAttakable(index: Int) -> Bool {
    for i in 0..<index {
        // arr[index] == arr[i] : 같은 열에 존재하는가?
        // abs(arr[index] - arr[i]) == abs(index - i) : 대각선방향으로 존재하는가?
        if arr[index] == arr[i] || abs(arr[index] - arr[i]) == abs(index - i) {
            return false
        }
    }
    return true
}

// DFS
func dfs(index: Int) {
    // 모든 행에 배치됬다면 탈출
    if index == N {
        result += 1
        return
    }
    // 주어진 행의 열에 모두 배치해본다.
    for i in 0..<N {
        // 이미 배치된 퀸의 공격범위라면 패스
        if visited[i] { continue }
        arr[index] = i
        // 배치 가능한 곳인지 확인한다.
        if checkAttakable(index: index) {
            visited[i] = true
            // 배치 후 그다음 행에 배치하귀위해 dfs 재귀호출
            dfs(index: index+1)
            // 그 전에 탐색했던 범위를 모두 배치가능으로 돌려놓는다.(백트래킹을 위해)
            visited[i] = false
        }
    }
}

dfs(index: 0)
print(result)