[알고리즘] 백트래킹

백트래킹이란?

해를 찾는 도중 조건을 만족하지 않으면(해가 될 것 같지 않으면) 그 경로를 포기하고 이전 단계로 돌아가 다른 해결책을 찾는 알고리즘 기법이다.(=가지치기)
반복문의 횟수를 줄일 수 있어서 효과적인 방법이다.

백트래킹은 모든 경우의 수를 하나씩 살펴보고, Decision space를 만들어 나간다.

💡 Decision space(의사결정 공간)란?

---

백트래킹에서 현재 상태에서 다음 단계로 진행할 수 있는 모든 가능한 선택지

예제 - Phone keypad 문제

입력된 숫자가 키패드에서 어떤 문자의 조합이 될 수 있는지 출력하는 문제
ex) 23 -> {AD, AE, AF, BD, BE, BF, CD, CE, CF}

우선 각 키패드 숫자를 key, 사용 가능한 문자를 value로 hashmap 생성

keypad

key	value
2	A, B, C
3	D, E, F
...	...
9	W, X, Y, Z

String input = "234";
List<String> output = new ArrayList<>();

void BT(int index , String letter) { // index : 몇 번째 숫자인지, letter : 몇번째 단계까지 만들어졌는지
	if (index == input.length()) {
            output.add(letter);
            return;
    }

    char num = input.charAt(index); // index = 0, num = 2
    String chars = keypad.get(num); // chars = "ABC"

    for (char c : chars.toCharArray()) {
        BT(index + 1, letter + c);
    }
}