백준 9663 백 트래킹 코틀린

백트래킹을 간단히 설명하자면 dfs 탐색에서 조건을 만족하는 부분만(깊이) 탐색한다고 생각하면 된다.

부모 노드의 자식 노드중 조건에 해당하지 않는 자식 노드가 있다면 그의 자식 노드들 또한 탐색하지 않는다.

 

가장 대표적인 문제가 n-queen문제이다.

n x n의 체스판에 n개의 퀸이 서로를 공격하지 못하게 하는 문제이다.

 

x o x x 

x x x o 

o x x x 

x x o x

 

위와 같이 퀸(o)이 서로 공격 못하는 경우의 수를 구하는 문제이다.

만약 퀸이(0.1)일 경우 다음 행에서는 같은 열과 대각선에 퀸을 놓을 수 없으므로

해당 부분을 자식으로 하는 경우를 제외한(백트래킹) 방법으로 탐색을 이어 나가면 된다.

ex) 

0                         0,1

                 /       /        \                   \

1          1,0(x)1,1(x) 1,2(x)              1,3(o)

                                             /       /        \     \

2 ..

3 ..

위와 같이  1,0(x)1,1(x) 1,2(x)에는 퀸을 놓는게 불가능 하기 때문에 하위 노드들을 탐색하지 않고 1,3의 하위 노드만 탐색하게 된다.

 

대각선에 있는지 판단 여부는 행과 열의 차이의 절대 값이 같으면 대각선에 있다.

ex)  |0-1| = 1, |1-0| =1, |1-2| = 1 이렇게 되면 대각선에 위치한지 판단 가능하다.

 

풀이)

var count = 0

fun main() {
    val n: Int = readLine()!!.toInt()
    val q = IntArray(n)
    dfs(q, 0)
    println(count)
}

fun check(q: IntArray, col: Int): Boolean {
    for (i in 0 until col) {
        if (q[i] == q[col]) return false // 같은 열인지
        if (q[i] - q[col] == col - i) return false // '\' 방향인지  abs를 통해 절대값을 사용해도 된다.
        if (q[col] - q[i] == col - i) return false // '/' 방향인지
    }
    return true
}

fun dfs(q: IntArray, col: Int) {
    val size = q.size

    for (i in 0 until size) {
        q[col] = i // 퀸 위치 표시
        if (check(q, col)) { // 해당 노드의 자식 노드의 탐색을 계속할지 여부
            if (col == size - 1) {
                count++ // 제일 마지막 줄인지 여부 (배치 완료)
            } else {
                dfs(q, col + 1)
            }

        }
    }
}