9663번: N-Queen - Kotlin (백트래킹)

9663번: N-Queen

문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

 위의 문제에서 가장 먼저 생각해야 할 것은 퀸들은 같은 열이나 행, 대각선에 존재할 수 없다는 것이다. 만약 이 문제를 일반적인 DFS방식으로 풀려고 한다면 퀸들을 배정하는데 모든 경우의 수를 계산해야 하기 때문에 너무 많은 시간이 걸릴 것이다. 이 문제의 해답은 기본적인 DFS의 방식을 그대로 가져가되 check 함수를 통해 다음 위치에 놓일 퀸의 위치가 합당한지를 확인받고 만약 그 위치가 부적절하다면 해당 자리에 퀸 놓는 것을 그만하고, 다른 위치에 퀸을 놓아보는 방식으로 문제를 해결하고 있다.

import kotlin.math.abs

lateinit var board : IntArray
var n = 0
var cnt = 0

fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    board = IntArray(n)
    recursive(0)
    println(cnt)
}

fun recursive(idx: Int) {
    if (idx == n) {
        cnt++
        return
    }
    for (i in 0 until n) {
        board[idx] = i
        if (check(idx)) recursive(idx + 1)
    }
}

fun check(idx: Int): Boolean {
    for (i in 0 until idx) {
        if (board[idx] == board[i] || idx - i == abs(board[idx] - board[i]))
            return false
    }
    return true
}