BackTracking Design Pattern에 대하여

BackTracking이란 Tree search 중에 DFS[depth first search]에서 파생한 디자인 패턴이다.

기본적으로 DFS를 실시하고 탐사 중에 Dead-End에 도달하면, 즉 더 깊은 depth에서 

해답을 찾을 수 없다고 판단하게 되면 아직 탐사하지 않은 노드를 자식 노드로 가지고 있는 노드를 

찾을 때까지 이전 탐사의 경로를 되짚어 간다. 그리고 이 것을 BackTracking 이라고 한다.

 

이 알고리즘 디자인 패턴에서 많이 언급되는 것이 N-Queens problem이다.

문제를 보면서 생각해보자.

 

N-Queens problem이란 (N*N) 크기의 체스판에 서로 공격이 불가능한

N개의 퀸을 배치할 수 있는 경우의 수를 구하는 문제이다.

 

먼저 a8에 퀸을 배치한 상황을 고려해보자.

a8에 퀸이 존재한다면 일단 같은 Row에는 퀸이 더이상 존재할 수 없기 때문에 다음 Row로 진행하면 되겠다.

이 상황을 트리로 생각해보면 루트 노드가 a8이 되고 자식 노드들이 7번 Row의 각 자리가 되겠다.

먼저 a7 child Node를 방문했다고 가정하면 a8과 같은 Column에 있기 때문에 퀸을 배치할 수 없다.

 

따라서, dead end node가 될 것이고 back tracking을 통해 a8로 이동, 다음 자식 노드를 탐사하면 되겠다.

b7 또한 배치할 수 없으므로 c7으로 이동하게 되고 이 노드는 배치 가능하므로 탐사를 진행하면 된다.

 

위와 같은 방식으로 진행하고 DFS의 깊이가 8이되면 count를 하나 추가하면서 탐사가 마쳤을때 count를

확인하면 이 문제의 해답을 얻을 수 있다.

 

마지막으로 구현하는 것 까지 해보자.

fun isSafe(c1: Coordinate, c2: Coordinate): Boolean {
    return !isSameColumn(c1, c2) && !isSameRow(c1, c2) && !isDiagonal(c1, c2)
}

fun isSameColumn(c1: Coordinate, c2: Coordinate): Boolean {
    return c1.y == c2.y
}

fun isSameRow(c1: Coordinate, c2: Coordinate): Boolean {
    return c1.x == c2.x
}

fun isDiagonal(c1: Coordinate, c2: Coordinate): Boolean {
    return abs(c1.x - c2.x) == abs(c1.y - c2.y)
}

data class Coordinate(
    val x: Int,
    val y: Int
)

 

코드 이해가 쉽게 나누어서 작성했다.

 

각 퀸은 같은 행, 같은 열에 존재하거나 한 대각선에 동시에 존재해서는 안된다.

따라서, 3조건을 모두 만족하지 않는 경우를 isSafe 함수가 true를 리턴하도록 했다.

fun dfs(history: MutableList<Coordinate>) {
    val row = history.size
    if(row == N) {
        println(history.toString())
        count++
        return
    }
    for(i in 0 until N) {
        val currentCoordinate = Coordinate(row, i)
        var temp = true
        history.forEach { h ->
            if(!isSafe(currentCoordinate, h)) {
                temp = false
            }
        }
        if(temp) {
            dfs(
                history.toMutableList().apply {
                    add(currentCoordinate)
                }
            )
        }
    }
}

 

DFS 함수는 지금까지 거쳐온 좌표 정보를 가지고 있고 사이즈가 N에 도달하면 

count를 증가시키고 리턴한다.

 

그렇지 않다면 다음 Row의 좌표들 중 history 좌표들과 isSafe의 파라미터로 연산하였을때

true인 것들에 한해서 DFS를 계속해서 진행한다.  

 

전체 코드는 다음과 같다.

const val N = 8
var count = 0
fun main() {
    for(i in 0 until N) {
        dfs(mutableListOf(Coordinate(0, i)))
    }
    println(count)
}

fun dfs(history: MutableList<Coordinate>) {
    val row = history.size
    if(row == N) {
        println(history.toString())
        count++
        return
    }
    for(i in 0 until N) {
        val currentCoordinate = Coordinate(row, i)
        var temp = true
        history.forEach { h ->
            if(!isSafe(currentCoordinate, h)) {
                temp = false
            }
        }
        if(temp) {
            dfs(
                history.toMutableList().apply {
                    add(currentCoordinate)
                }
            )
        }
    }
}

fun isSafe(c1: Coordinate, c2: Coordinate): Boolean {
    return !isSameColumn(c1, c2) && !isSameRow(c1, c2) && !isDiagonal(c1, c2)
}

fun isSameColumn(c1: Coordinate, c2: Coordinate): Boolean {
    return c1.y == c2.y
}

fun isSameRow(c1: Coordinate, c2: Coordinate): Boolean {
    return c1.x == c2.x
}

fun isDiagonal(c1: Coordinate, c2: Coordinate): Boolean {
    return abs(c1.x - c2.x) == abs(c1.y - c2.y)
}

data class Coordinate(
    val x: Int,
    val y: Int
)

 

N = 8일때 연산을 해보면 답은 92인 것을 확인할 수 있었고 dfs가 2056번 불린 것을 확인할 수 있었다.

총 경우의 수가 (8^8=16,777,216) 인 것을 볼때 상당한 이점이 있는 것을 확인 할 수 있다.

N = 10일때 또한 연산해보면 (10^10 = 10,000,000,000)의 경우의 수를 가졌지만 35538번 dfs가

불린 것을 확인했다.