[백트래킹]

가능한 모든 방법을 탐색한다!

• 하지만 완전 탐색 (DFS, BFS)과는 달리 가능성이 있는 경로들만 검사.
• 가능성을 가지치기 (Prunning)를 통해 경로를 결정.
• 이 가지치기를 얼마나 잘하냐가 핵심.
• 참고 블로그 1, 참고 블로그 2, 참고 블로그3

N과 M

• 1부터 N까지의 수 중에서 중복 없이 M개를 고르는 수열을 출력하는 문제

참고 코드
void func(int k) {
    for(int i=1; i<=n; i++){
        if(!visited[i]) {
            arr[k] = i;
            visited[i] = 1;
            func(k+1);
            visited[i] = 0;
        }
    }
}

vs 완전 탐색 (or DFS)

• 완전 탐색의 경우에는 해당하는 모든 경로 탐색
• 반면에 백트래킹은 위의 예제와 같이 분기를 나누어서 필요한 경우만 탐색

예제 문제

• 백준 단계 14 백트래킹