10. [Java] Backtracking (퇴각 검색)

Backtracking

백트래킹이란 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고,
만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다.

• 가장 중요한 점은 제한 조건을 위배한다면 그 노드를 제외한다는 점이다,.
• 현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의 수가 더이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것
• 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)이라고 한다.
• DFS를 통해 모든 노드를 깊이 우선 탐색을 하면서 더 이상 필요 없는 부분을 쳐내는 행위를 백트래킹(가지치기)이라고 생각하면 된다.
  
  DFS와 Backtracking의 다른점
• DFS는 가능한 모든 경우의 수를 탐색한다. 그래서 시간이 많이 걸린다
• 백트래킹은 탐색을 하다가 불필요한 탐색이라고 생각하면 다른 루트를 탐색한다
  -> 얼마나 가지치기를 잘하느냐가 제일 중요하다.

---

• 완전 탐색 기법
  • 답이 될 수 없는 경우를 미리 체크해서 효율성을 좋게 만들 수 있다.
• 일반적으로 DFS와 동일하게 재귀 함수로 구현한다.
• 상황에 따라 다르지만, 일반적으로 시간복잡도가 매우 큰 편이다,
• 파라미터로 현재의 위치, 상태 등 현재 탐색에 독립적인 데이터를 넘긴다.
• 방문 체크를 사용한다면, 해당 정점을 방문한 후에 원복(원상복구)하는 로직이 필요할 수 있다.

 

• 대문자 알파벳 A,B,C,D 를 사용해서 만들 수 있는 4글자 문자열을 전부 출력하는 문제를 풀어볼 수 있다.
• 단, 각 알파벳은 무한대로 사용 가능하다.

public class practice {

    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() == 4) {
            System.out.println(s);
            return;
        }

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

 

결과화면

만약 각 알파벳을 무한대로 사용가능한 게 아니라 한번씩만 사용가능하도록 조건을 바꾼다면 어떻게 될까?

바뀐 코드

public class test {

    private static final char[] alpha = {'A', 'B', 'C', 'D'};

    private static final int LENGTH = 4;

    private static final boolean[] used = new boolean[4]; // true/false 판별 코드

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

    private static void backtrack(String s) {
        if (s.length() == 4) {
            System.out.println(s);
            return;
        }
		
        // 변경 및 추가된 코드
        for (int i = 0; i < 4; i++) {
            if (!used[i]) {
                used[i] = true;
                backtrack(s + alpha[i]);
                used[i] = false;
            }
        }
    }
}

Backtracking(퇴각 검색) 구현 방법

• 방문 체크 용(재방문 방지) 배열을 만든다. (필요한 경우)
• 현재 상태(정점)를 파라미터로 넘겨 받는 함수(메소드)를 정의한다.
  • 현재 상태 정보는 하나가 아닐 수 있다.
• 함수(메소드) 내부에서..
  • 원하는 데이터가 완성이 되었으면 Return한다.
  • For문 내부에서
    • 현재 정점의 방문 체크를 한다. (필요한 경우)
    • 현재 상태를 파라미터로 넘기면서 재귀 함수를 호출한다.
    • 현재 정점의 방문 해제를 한다. (필요한 경우)