[ 백트래킹 ] N과 M

Backtracking 이란?

백트래킹은 모든 가능한 경우를 탐색하되 조건을 만족하지 않는 경로를 미리 차단(가지치기)하는 알고리즘이다. 쉽게 말해

• 가능한 선택지를 따라가며 시도한다.
• 조건에 어긋나면 되돌아온다. -> 백트래킹
• 조건을 만족하면 결과를 기록한다.

DFS(깊이 우선 탐색)을 기반으로 구현한다.

 

우선 문제를 분석해보자.

[백준 15649]https://www.acmicpc.net/problem/15649

"1부터 N까지 자연수 중에서 중복 없이 M개를 고른 모든 수열을 출력하라"

N개의 수 중에서 M개를 뽑되 순서가 중요하고, 중복은 허용되지 않는다.

 

해당 문제는 겉으로 보기엔 단순한 모든 경우 탐색 문제처럼 보이지만 실제로는 Combinatorial Explosion 다루는 예제처럼 보인다. 모든 경우를 탐색하되 불필요한 탐색은 하지 않는 점을 고려하여 백트래킹을 적용했다.

 

DFS(재귀)를 이용

각 재귀 단계(depth)는 현재까지 선택된 숫자의 개수를 의미한다.

Depth가 M이 되면 수열이 완성된 것.

 

방문 체크 배열로 중복 방지

이미 선택된 숫자는 다시 고르지 않아야 하므로, visited[i] 배열을 사용한다.

재귀가 끝나면 상태를 복원(visited[i] = false) 해야한다. 이게 바로 백트래킹이다.

 

결과를 누적해 출력

매번 println()을 사용하면 I/O 오버헤드가 크기 때문에 StringBuilder를 사용해 한 번에 출력한다.

 

import java.lang.StringBuilder

fun main() {
	val (n, m) = readln().split(" ").map { it.toInt() }
    val visited = BooleanArray(n + 1)
    val result = IntArray(m)
    val sb = StringBuilder()
    
    fun dfs(depth: Int) {
    	if(depth == m) {
        	sb.append(result.joinToString(" ")).append('\n')
            return
        }
        
        for(i in 1..n) {
        	if(!visited[i]) {
            	visited[i] = true
                result[depth] = i
                dfs(depth + 1)
                visited[i] = false
            }
        }
    }
    
    dfs(0)
    print(sb)
}

 

시간 복잡도 O(N!) - 순열 생성

공간 복잡도 O(N) - visited 배열 + 재귀 스택

 

보통 재귀 함수를 사용하면 메모리적으로 시간적으로 효율이 좋지 않다고 알고 있다. 그래서 dfs 방식중인 stack 자료구조를 이용하여 재귀와 스택의 시간, 공간 복잡도를 비교해보았다.

import java.util.Stack

data class State(
	val depth: Int,
    val result: IntArray,
    val visited: BooleanArray
)

fun main() {
	val (n, m) = readln().split(" ").map { it.toInt() }
    val sb = StringBuilder()
    val stack = Stack<State>()
    
    stack.push(State(0, IntArray(m), BooleanArray(n + 1)))
    
    while(stack.isNotEmpty()) {
    	val (depth, result, visited) = stack.pop()
        
        if(depth == m) {
        	sb.append(result.joinToString(" ")).append('\n')
            continue
        }
        
        for(i in n downTo 1) {
        	if(!visited[i]) {
            	val newResult = result.copyOf()
                val newVisited = visited.copyOf()
                newResult[depth] = i
                newVisited[i] = true
                stack.push(State(depth + 1, newResult, newVisited))
            }
		}
    }
    
    print(sb)
}

 

시간 복잡도

재귀 함수

모든 가능한 수열을 탐색한다.

 

반복 스택

동일한 노드를 동일한 순서로 탐색한다.

 

시간복잡도는 동일하다. 재귀 호출 오버헤드(함수 호출 + 스택 프레임 생성)가 미세하게 존재하긴 하지만
N <= 8 수준에서는 차이가 0에 가깝다.

 

공간 복잡도

현재 조건에서는 명시적 스택에 더 많은 상태 정보를 넣기 때문에 재귀가 메모리가 더 효율적으로 보인다.

 

결론

이 문제(N <= 8)에서는 재귀가 훨씬 간결하고 효율적으로 보인다. 스택을 사용하는 건 재귀 한계를 초과하는 깊이일 때만 이점이 있어 보인다. 상황에 따라 조건에 따라 여러 알고리즘을 생각해내고 시간과 메모리 상태를 분석 후에 빠르게 판단하는 것 또한 문제 해결력으로 보인다.