백트래킹

백트래킹(Backtracking) 알고리즘

백트래킹은 문제 해결에 사용되는 알고리즘 중 하나로, 가능한 모든 후보군을 검사하여 해결책을 찾아가는 과정에서 불필요한 경우의 수를 배제해나가는 기법입니다

이 알고리즘은 깊이 우선 탐색(DFS)과 밀접한 관련이 있으며, DFS의 탐색 경로가 더 이상 조건에 부합하지 않게 되면, 다시 되돌아가면서 다른 가능성을 탐색하는 방식입니다.

백준의 15649번 문제인 N과 M (1)를 백트래킹을 사용하여 푸는 예시로 볼 수 있습니다.

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
• 조건 : 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

이 문제의 수열을 구하는 메소드는 아래와 같이 작성할 수 있습니다.

fun backtracking(n: Int, m: Int, usedList: MutableList<Int>) {
    if (usedList.size == m) {
        println(usedList.joinToString(" "))
        return
    }

    for (i in 1..n) {
        if (!usedList.contains(i)) {
            usedList.add(i)
            backtracking(n, m, usedList)
            usedList.removeLast()
        }
    }
}

이 코드의 핵심은 재귀적으로 usedList 리스트에 숫자를 추가하고, usedList의 길이가 m과 같아지면 결과를 출력하고, 다시 해당 숫자를 usedList에서 제거하는 것입니다.

이렇게 함으로써 모든 가능한 수열을 생성하면서 중복을 제거할 수 있게 됩니다.

따라서 이 코드는 가능한 모든 경우를 생성하고, 중복과 같은 불필요한 경우를 미리 제거하여 계산을 최소화하는 백트래킹 알고리즘의 예시로 볼 수 있습니다.