세번째 시간이 돌아왔습니다.
이번엔 백트래킹, Backtracking, 퇴각 검색인데요.
DFS랑도 같이 섞어 쓰기도 하고, 코테에서 자주 등장하는 것 같으니까 :))
한번 가볼까요 ? 따라오세요 얼른. Come on.

1. 백트래킹?

퇴각 검색이라는 뜻인데요, 특징들을 한번 살펴보겠습니다.

• 완전 탐색 기법이기 때문에 일반적으로 시간복잡도가 매우 큰 편입니다.
  • 답이 될 수 없는 경우를 미리 체크해 효율성을 높일 수 있습니다. (일종의 가지치기)
  • 그래서 엄청나게 큰 사이즈의 검색으로 주어지지 않아요 ㅎ3ㅎ
• DFS랑 비슷하게 재귀 함수로 구현합니다.
• 파라미터로 현재의 위치, 상태 등 현재 상태의 독립적인 데이터를 넘깁니다.
• 방문 체크를 사용한다면, 정점 방문 후에 방문을 원복하는 로직이 필요한 경우가 있습니다.

2. 알파벳 문제로 알아보자

대문자 알파벳 A, B, C, D를 사용해 만들 수 있는 4글자 문자열을 전부 출력하는 문제를 풀어봅시다.
단, 각 알파벳은 무한대로 사용할 수 있다고 가정합니다.

1. 중복을 허용하는 경우

backtrack("") 을 호출하면, for문을 돌면서 하나씩 문자열을 채웁니다.
재귀로 구성했기 때문에 계속 깊게 들어가다가, 조건인 4글자를 채우면 바로 전으로 리턴하여 다음 인덱스로 들어갑니다.
이렇게 순차적으로 완전탐색을 진행하게 됩니다.

코드로 살펴볼까요?

class Backtracking {
    private static final char[] alpha = {'A', 'B', 'C', 'D'};
    private static final int LENGTH = 4;

    public static void main(String[] args) {
        backtrack("");
    }

    private static void backtrack(String s) {
        if (s.length() == LENGTH) {
            System.out.println(s);
            return;
        }

        for (int i = 0; i < LENGTH; i++) {
            backtrack(s + alpha[i]);
        }
    }
}

2. 중복을 허용하지 않는 경우

중복되는 알파벳을 허용하지 않는 (ex. "AAAA", "AABC", "ABCC" .. ) 4글자 문자열을 출력하려면 어떤 부분이 변경되어야 할까요?

방문 체크 배열을 사용하면서 재귀 함수에서 리턴되면 방문 상태를 원복하는 로직을 사용하면 됩니다!

코드로 볼까요?

class Backtracking {
    private static final char[] alpha = {'A', 'B', 'C', 'D'};
    private static final int LENGTH = 4;
    private static final boolean[] used = new boolean[4]; // 방문 체크용 배열
    public static void main(String[] args) {
        backtrack("");
    }

    private static void backtrack(String s) {
        if (s.length() == LENGTH) {
            System.out.println(s);
            return;
        }

        for (int i = 0; i < LENGTH; i++) {
            if (!used[i]) { // 방문하지 않았다면
                used[i] = true; // 방문 체크 후
                backtrack(s + alpha[i]); // 재귀로 들어감
                used[i] = false; // 리턴되면 원복시킴
            }
        }
    }
}

3. Ending

백트래킹은 코테에서 많이 등장하는 것 같다 ,, 익숙하게 더 연습해야지 냠 냠