[알고리즘] 백트래킹(Back Tracking)이란?

백트래킹(Back Tracking)

백트래킹은 깊이 우선 탐색(DFS)를 진행하며 탐색 중인 경로에 답이 없다고 판단되면 해당 노드를 제거하고, 탐색을 시작했던 부모 노드에서 바른 방향으로 다시 탐색합니다.

여기서 더 이상 탐색할 필요가 없는 노드를 제외하는 것을 가지치기(Pruning)이라 하고

해당 경로에 답이 있다고 판단되는 경우에는 유망하다(Promising)이라고 합니다.

즉, 백트래킹은 DFS탐색을 진행하며 유망한 조건을 만족하는 방향으로만 탐색하는 알고리즘입니다.

 

 

백트래킹 탐색 과정

ACG라는 단어를 찾는다고 가정했을 시 다음과 같은 순서로 탐색을 진행합니다.

1. DFS탐색을 진행하여 "A"노드에서 "B"노드를 방문합니다.
2. A다음 찾는 단어는 C로 "B"노드가 아니기 때문에 가지치기를 하고 부모 노드 "A"로 돌아갑니다.
3. 그 다음 인접한 "C"노드를 방문합니다.
4. A다음 찾고자 하는 단어가 C로 해당 노드는 유망하기 때문에 탐색을 진행합니다.
5. 인접한 "F"노드를 방문하지만 C다음 찾고자 하는 단어는 G로 해당 노드를 가지치기를 하고 부모 노드 "C"로 돌아갑니다.
6. 그 다음 인접한 "G" 노드를 방문하고 찾고자하는 단어 ACG를 찾아 종료합니다.

 

예제 코드

다음 코드는 백준의 N과 M(1)문제로 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 출력하는 코드입니다.

import java.util.Scanner;

public class Backtracking {
    public static int[] arr;
    public static boolean[] visited;

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        int n = input.nextInt();
        int m = input.nextInt();

        arr = new int[m];
        visited = new boolean[n];
        dfs(n, m, 0);
    }

    public static void dfs(int n, int m, int depth) {
        if (depth == m) { // 배열의 길이 m만큼 다 찼을 경우
            for (int node : arr) {
                System.out.print(node + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true; // 방문 여부 표시
                arr[depth] = i + 1; // arr[인덱스]에 해당 값을 넣어 준다.
                dfs(n, m, depth + 1); // arr배열의 다음 칸을 채우기 위해 재귀
                visited[i] = false; // 반복문이 끝나면 방문 여부를 false로 초기화하여 재사용한다.
            }
        }
    }
}