백트래킹 알고리즘

백트래킹 알고리즘은 해결하고자 하는 문제의 해답을 찾아가는 과정에서, 어떤 조건을 만족하지 않으면 해당 경로를 포기하고 다시 돌아가서 다른 경로를 찾는 방법입니다.

이러한 방법은 모든 가능한 경우의 수를 전부 탐색하지 않고도 해답을 찾을 수 있게 해줍니다.

이 방법은 대표적으로 스도쿠, N-Queen, 암호해독 등 문제에서 많이 사용됩니다.

백트래킹 알고리즘 추천 문제 (Kotlin)

https://www.acmicpc.net/problem/15649

fun main() {
    val br = System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(" ").map { it.toInt() }
    val tmp = (1..n).joinToString("")
    findNew(tmp,"",m)
}

fun findNew(str: String, currentStr: String, m: Int) {
    if (m == 0){
        println(currentStr.trim())
        return
    }
    for ((i,value) in str.withIndex()){
        val remain = str.substring(0,i) + str.substring(i+1)
        findNew(remain, "$currentStr $value", m-1)
    }
}

https://www.acmicpc.net/problem/1182

var count = 0
fun main() {
    val br = System.`in`.bufferedReader()
    val (n, s) = br.readLine().split(" ").map { it.toInt() }
    val arr = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    search(0, arr, 0, s, false)
    println(count)
}

fun search(idx: Int, arr: IntArray, sum: Int, s: Int, flag: Boolean) {
    if (sum == s && flag) count++
    if (idx == arr.size) return
    search(idx + 1, arr, sum, s, false)
    search(idx + 1, arr, sum + arr[idx], s, true)
}

https://www.acmicpc.net/problem/10971

var count = Int.MAX_VALUE
fun main() {
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val arr = Array(n) { IntArray(n) }
    for (i in arr.indices) arr[i] = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    for (i in 0 until n) {
        val visited = BooleanArray(n) { false }
        search(i, arr, i, visited, 0)
    }
    count = if (count == Int.MAX_VALUE) 0 else count
    println(count)
}
fun search(start: Int, arr: Array<IntArray>, now: Int, visited: BooleanArray, sum: Int) {
    visited[now] = true

    if (visited.count { it == true } == arr.size) {
        if (arr[now][start] != 0) count = minOf(count, sum + arr[now][start])
        return
    }


    for (i in arr[now].indices) {
        val cost = arr[now][i]
        if (!visited[i] && cost != 0) {
            search(start, arr, i, visited, sum + cost)
            visited[i] = false
        }
    }
}

---

추가예정

백트래킹 알고리즘의 시간 복잡도

백트래킹 알고리즘의 시간 복잡도는 문제의 상황과 조건에 따라 달라집니다.

하지만, 일반적으로 백트래킹 알고리즘은 모든 경우를 다 탐색하는 완전 탐색 방법보다 효율적입니다.

이는 백트래킹 알고리즘이 해답에 더 가까운 경로를 더 빨리 찾기 때문입니다.

하지만, 백트래킹 알고리즘의 경우, 최악의 경우 모든 경우를 다 탐색해야 할 수도 있습니다.

따라서, 시간 복잡도는 백트래킹 알고리즘을 사용하는 문제에 따라 다름니다

결론

백트래킹 알고리즘은 문제 해결에 있어서 중요한 알고리즘 중 하나입니다.

이번 포스팅에서는 백트래킹 알고리즘의 개념과 추천 문제를 알아보았습니다.

또한, 백트래킹 알고리즘을 적용할 때 중요한 것은 가능한 모든 경우의 수를 탐색하는 것이 아니라, 불필요한 경우의 수를 미리 배제하고 필요한 경우의 수만 탐색하도록 하는 것입니다.

이를 위해서는 각 상황에서 어떤 조건을 만족하는지를 잘 고려하여 코드를 작성해야 합니다.

백트래킹 알고리즘은 재귀적인 구조를 가지고 있으며, 대체로 코드가 간결하고 직관적입니다. 따라서, 문제 해결에 있어서 백트래킹 알고리즘을 적용할 수 있는 경우가 많습니다.

하지만, 백트래킹 알고리즘은 문제의 조건과 상황에 따라서 시간 복잡도가 급격히 증가할 수 있습니다. 따라서, 문제를 푸는데 있어서 최적의 알고리즘을 선택하는 것이 중요합니다.