백트래킹

백트래킹 (Back Tracking)

 

 

1)  백트래킹란?

백트래킹은 모든 경우의 수를 탐색하되,
조건을 만족하지 않는 경우 탐색을 중단하고 이전 단계로 되돌아가는 방식의 탐색 알고리즘이다.

DFS 기반의 완전 탐색 기법 중 하나로, 불필요한 탐색을 줄여주는 가지치기(pruning) 기법이 포함된다.

 

 

 

 

2)  백트래킹 동작원리

 

1. 가능한 모든 경우를 시도한다 (DFS 기반 탐색).

2. 탐색 도중 조건에 맞지 않는 경우 더 이상 진행하지 않고 되돌아간다 (backtrack).

3. 조건을 만족하는 경우 정답 처리한다.

4. 다음 탐색을 위해 상태를 복구하고(undo), 새로운 경우의 수를 시도한다.

 

 

// 백트래킹 구조

void backtrack(int depth) {
    if (종료 조건) {
        정답 처리;
        return;
    }

    for (int i = 선택 범위) {
        if (유망하지 않으면 continue); // 가지치기
        상태 저장;
        backtrack(depth + 1);
        상태 복구; // 백트래킹
    }
}

 

 

 

3)  사용 조건

 

1. 모든 경우의 수를 탐색해야 하는 문제

2. 단, 중간에 불필요한 탐색을 줄일 조건이 존재할 때 유리함

 

 

 

 

4)  시간 복잡도

 

모든 경우 탐색일 때, 최대 O(2ⁿ) ~ O(n!) 까지 발생할 수 있음
하지만 조건이 강하면 가지치기로 탐색 공간이 급감할 수 있음

 

 

 

 

 

5)  특징

 

항목	내용
기반 알고리즘	DFS (재귀적 구조)
핵심 개념	상태 저장 → 탐색 → 조건 불만족 시 복귀 (Undo)
장점	완전탐색보다 빠르다 (가지치기)
단점	조건이 없거나 가지치기를 못하면 완전탐색과 같음
사용 자료구조	배열, visited 배열, 재귀 함수

 

 

 

 

 

 

 

 

 

 

관련 문제

https://devwarriorjungi.tistory.com/entry/%EB%B0%B1%EC%A4%80-9663-Java-N-Queen

[백준 9663] Java - N-Queen