백트래킹(Backtracking) (with 예제 Leetcode 17. Letter Combinations of a Phone Number)

백트래킹이란 일반적으로 모든 가능한 해를 시도해보며, 조건을 만족하는 해를 찾는 알고리즘이다. 조건을 만족하지 않으면 이전 단계로 돌아가서 다른 가능성을 시도하하기 때문에 "백트래킹(backtrack)"이라고 한다. DFS는 모든 경로를 탐색하는데 백트래킹은 조건이 있어 모든 경로가 아닌 조건에 맞는 경로만 탐색한다는 차이점이 있다. 이전상태로 돌아오는 작업이 필요하기 때문에 스택(혹은 재귀)를 사용하는 DFS를 이용해서 주로 구현한다. 

DFS를 이용한다면 기본적으로 구성은 비슷하다. 탐색을 멈출 조건문이 제일 처음에 들어가고, 모든 노드 방문을 위한 반복문, 내부에서 본인을 재귀 호출, 요구사항에 맞는 값 리스트에 추가해서 리턴하거나 프린트 
말로만 설명하면 헷갈리니까 리트코드에서 예제를 하나 가져와서 풀어보자.

17. Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
 
Input: digits = ""
Output: []

23을 입력했을경우 2에 해당하는 a, b, c 와 3에 해당하는 d, e, f 의 모든 조합을 구하는 백트래킹 문제이다. (물론 조합으로도 풀 수 있음)
먼저 숫자와 알파벳을 딕셔너리로 매핑해놓자. 여러 방법이 있겠지만 바로 매칭되기에는 딕셔너리가 제일 편한것 같다.

mapping = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}

그 다음 백트래킹 함수를 짜야하는데 종료조건을 생각해보자. 입력으로 주어지는 digits의 길이만큼 문자가 조합되기 때문에, 몇번째 탐색인지 인덱스와 digits 길이가 같으면 지금까지 누적된 알파벳을 리턴 할 수 있게 했다. 그 다음 매핑해놓은 알파벳들을 순서대로 반복문 돌면서 인덱스도 1씩 증가시키면서 각 알파벳을 누적해 더할 수 있도록 했다. 

def backtracking(index, accum):
    if index == len(digits):
        return res.append(accum)

    for alpha in mapping[digits[index]]:
            backtracking(index + 1, accum + alpha)

예제의 23이 들어왔다고 하고 백트래킹 함수를 호출한다  backtracking(0, "") 

처음에 인덱스 0으로 백트래킹 함수를 호출한다면 digits의 0번째인 "2" 값이 들어오게 되고 이는 곧 매핑 값인 "abc" 가 된다. alpha는 a, b, c를 순서대로 순회할 것이다. 반복문 안에서는 백트래킹을 또 호출하는데 이때 인덱스를 1 증가시키고 현재 알파벳인 a 를 보낸다.

backtracking(1, "a") 

현재 인덱스는 1이기 때문에 if문을 건너뛰고 아래 반복문으로 내려간다. 인덱스가 1이기 때문에 digits의 1번째 값인 "3"이 들어오고 "def" 중의 첫번째 값인 d가 alpha가 된다. 그럼 현재 accum의 값인 a 와 d 가 더해져서 "ad" 값과 인덱스에 2 값이 들어가게 된다. 

backtracking(2, "ad")

현재 인덱스는 2이고 digits의 길이도 2이기 때문에 if문에 걸린다. 지금까지 누적된 알파벳을 결과 리스트에 넣어 리턴한다. 여기서 이전 작업인 backtracking(1, "a")의 반복문으로 돌아가게 된다. 

돌아온 backtracking(1, "a")

backtracking(2, "ad")가 종료 되었기 때문에 다음 반복문을 수행한다. d 다음은 e 값이 alpha에 할당되고 backtracking(2, "ae") 가 호출된다. 

backtracking(2, "ae")

if문에 걸려 "ae"를 결과 리스트에 넣어 리턴한다. 여기서 이전 작업인 backtracking(1, "a")의 반복문으로 돌아가게 된다...

이후 f 까지 들어가서 af가 리스트에 추가되고 나면 인덱스 1 일때의 반복문이 종료되며 backtracking(1, "a") 의 작업이 모두 끝난다. 그러면 다시 backtracking(1, "a") 의 이전 작업인 backtracking(0, "") 이었을때의 반복문으로 돌아가게 되며 a는 작업이 끝났으므로 "b"가 들어가서  backtracking(1, "b") 라는 작업이 시작된다. 이후 계속 동일한 작업이 반복.. 결론적으로 우리가 얻고자 하는 모든 조합인 ["ad","ae","af","bd","be","bf","cd","ce","cf"] 이런 리스트를 얻을 수 있다. 재귀가 코드는 짧지만 내부 동작을 풀어쓰려면 복잡한 편이다. 처음에는 하나하나 써보면서 차근차근 이해 하는 것을 추천한다. 최종코드는 다음과 같다. 

class Solution(object):
    def letterCombinations(self, digits):
        if not digits:
            return []

        mapping = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz"
        }

        res = [] 
        def backtracking(index, accum):
            if index == len(digits):
                return res.append(accum)

            for alpha in mapping[digits[index]]:
                    backtracking(index + 1, accum + alpha)

        backtracking(0, "")
        return res