백트래킹(Backtracking)

호수·2023년 11월 3일

JAVA 알고리즘

목록 보기

4/67

백트래킹 자바 코드

백트래킹: 모든 후보군을 따라 들어가며 탐색하는 알고리즘

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static int[] arr = new int[10];
    static boolean[] isUsed = new boolean[10];

    public static void func(int k) {
        if (k == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!isUsed[i]) {
                arr[k] = i;
                isUsed[i] = true;
                func(k + 1);
                isUsed[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        func(0);
    }
}

백트래킹(backtracking)이란?

솔루션을 찾는 과정에서, 유망(promising)하지 않은 후보해에 대해 대해 빠르게 포기하고 이전 단계로 되돌아(back track)가 다른 후보해를 찾는 알고리즘 기법
즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.

이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다.

일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있습니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.

DFS와 Backtracking

DFS : 완전 탐색을 기본으로 하는 그래프 순회 기법으로, 모든 노드를 방문하는 것을 목표로 한다.

Back-tracking : 불필요한 탐색을 하지 않고, 이전 단계로 돌아와 다른 후보해를 탐색해 나가는 방법
=> 일단 가보고 후보해가 될 수 없으면 다음 단계로 진행하지 않고 되돌아 나온다.

DFS와 Back-tracking 둘다 재귀 호출 형태로 자주 구현이 되기 때문에 헷갈린다.
두 알고리즘은 사용 목적에 차이가 있다.

DFS : 깊이 우선 탐색하여 모든 노드를 방문하는 것을 목표로 한다.
Backtracking : 불필요한 탐색을 하지 않기 위해, 유망하지 않은 경우의 수를 줄이는 것을 목표로 한다.

DFS는 완전 탐색을 목표로 하는 알고리즘이기 때문에 자원 소모가 굉장히 심하다. 그래서 어떤 제약 조건에 맞는 해답을 찾기 위해서 DFS와 Back-tracking 기법을 혼용해서 사용한다.
=> 가지 치기를 통해서 얻은 그래프에 대해서 다시 DFS 탐색을 하면서 불필요한 탐색을 줄여 나간다.

다음 그림은 DFS와 Back tracking을 이용해서 'AIR' 라는 단어를 찾는 과정을 나타낸 것이다.