[Leetcode] 17. Letter Combinations of a Phone Number

DFS와 백트랙킹

깊이 우선 탐색(DFS)DFS는 가능한 모든 경로(후보)를 탐색합니다. 

따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못합니다.따라서 N! 가지의 경우의 수를 가진 문제는 DFS로 처리가 불가능할 것입니다.

 

백트랙킹

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아갑니다.

즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.

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

 

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

 

어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 갑니다.

해가 될 가능성이 있으면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning) 한다고 하는 것입니다.

 

답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것을 백트래킹이라고 생각하면 됩니다.

주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있습니다.

 

문제풀이

그럼 문제를 DFS를 사용해서 풀어봅시다.

해당 문제에 dfs를 적용하면 위 그림처럼 표현할 수 있습니다.

 

"23"을 입력받았다고 해봅시다. 먼저 번호 2에 해당하는 "abc"를 차례대로 순회해야 합니다. 그렇게 때문에 for문이 각각 필요합니다. a,b,c는 각자 d,e,f,와 연결되어있는 그래프라고 생각해봅시다. dfs방법을 사용해서 연결되어 있는 노드를 순회해야 하기 때문에 dfs를 위한 재귀함수가 필요합니다. 이렇게 코드를 짜보겠습니다.

 

def letterCombination(digits):                        
    def dfs(index,path):
        if len(path)==len(digits): 
            result.append(path)
            return
        for i in range(index,len(digits)): #입력한 문자열 길이만큼  
            for j in dic[digits[i]]:
                dfs(i+1,path+j) #문자열 element에 해당하는 dic의 value값을 path에 더해서 보냄
                #중복문자 방지
                
    if not digits: #digit이 존재 x = True 이기 때문에 if문이 실행됨
        return []
    
    dic = {"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs",r"8":"tuv","9":"wxyz"}
    
    result=[]
    dfs(0,"")
    
    return result