[ LeetCode] Letter Combinations of a Phone Number 문제 풀이(Backtracking/백트레킹/Python/파이썬)

< 문제 설명 : Letter Combinations of a Phone Number >

 

2에서 9까지의 숫자를 포함하는 문자열이 주어지면 숫자가 나타낼 수 있는 모든 가능한 문자 조합을 반환합니다.

어떤 순서든 답을 반환하세요.

숫자 대 문자 매핑(전화 버튼과 마찬가지로)이 아래에 나와 있습니다. 1은 어떤 문자에도 매핑되지 않습니다

 

예시

 

 

 

문제 풀이

이 문제의 예시들을 보면

만약 입력 digits가 23이라면 2에 매핑되는 문자는 abc이고 3에 매핑되는 문자는 def이므로 이 문자들을 조합한 결과를 반환해야 하고입력이 없다면 만들 수 있는 문자 조합이 없기 때문에 빈 리스트를 반환해야 합니다

숫자 입력은 길이 4까지 받을 수 있고 digits는 2부터 9까지 입니다.

관련 주제는 다음과 같고 저는 Backtracking을 사용하여 문제를 풀었습니다.

Related Topics : Hash Table / String / Backtracking

 

백트레킹(Backtracking)이란

• 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙)해 정답을 찾아가는 알고리즘
• 백트래킹은 깊이 우선 탐색(DFS)과 같은 방식으로 탐색하는 모든 방법을 뜻하며, DFS는 백트래킹의 골격을 이루는 알고리즘

 

 

백트레킹(Backtracking) 구현 방법

     - 백트래킹은 주로 재귀로 구현, 알고리즘마다 DFS변형이 조금씩일어나지만 기본적으로 모두 DFS범주

 

     - DFS로 탐색을 시도, 가능성이 없는 후보는 즉시 포기하고 백트래킹한다면 트리의 불필요한 거의 대부분을 버릴수 있음

 

     - DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고,

        그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있음

 

(백트레킹 설명 출처- https://chanhuiseok.github.io/posts/algo-23/)

 

 

 

 

백트레킹(Backtracking)을 문제에 적용한 방법

백트레킹을 하기위해서는 깊이 우선 탐색 중에 절대 답이 될수 없는 후보는 탐색하지 않고 되돌아가야하는데

이때 절대 답이 될수 없는 제약 조건들을 만들어야 합니다

 

이문제에서 걸 수 있는 제약조건은 두 가지인데

첫 번째는 입력 digits와 문자 조합된 결과는 길이가 같아야 합니다

숫자가 3개 입력되면 만들어질 수 있는 문자 조합들도 3글자가 돼야 합니다

두 번째  제약조건은 첫 번째 두번째 세번째에 올수 있는 문자들이 한정되어있습니다

264가 입력되었다면 첫번째 문자는 abc 중 하나두 번째 문자는 mno 중 하나세 번째 문자는 ghi 중 하나가 되어야 하고순서가 바뀌어서는 안 됩니다

 

이러한 제약조건을 가지고 깊이 우선 탐색이 진행되는 과정을 그림으로 살펴보겠습니다

우선 첫 번째 올 수 있는 문자 ABC 중  A로 탐색을 시작합니다

두 번째로 가능한 letter 중 하나인 m을 사용하여 조합합니다.

세 번째로 가능한  letter 중 하나인 g를 사용하여 조합합니다.

현재 문자 조합은 두 가지 제약조건 때문에 더 이상 아래층으로 탐색할 수 없습니다.

 입력 digits와 문자 조합은 길이가 같아야 하는데 숫자가 3개 입력되어 만들어질 수 있는 문자 조합들도 3글자이고

두 번째  제약조건은 첫번째 두번째 세 번째에 올 수 있는 문자들이 한정되어 있는데 모두 사용한 상황이므로

더 이상 탐색할 수 있는 노드가 없어 다시 'am'으로 백 트레킹 하여 돌아갑니다.

아래는 탐색과정을 볼 수 있는 이미지입니다.

 

 

 

 

 

 

 

 

Pseudo code (DFS 재귀 호출 중 백트레킹) 

이 알고리즘을 구현한다면 우선 두 개 함수가 있습니다

letters combinations 함수에서는 필요한 변수들과 예외처리 그리고 깊이 우선 탐색을 시작하기 위해 DFS를 호출합니다

dfs함수는 재귀 호출로 깊이 우선 탐색을 진행하고 제약조건으로 백 트래킹 하는 함수입니다

dic은 문제에서 제시한 digits와 문자들 매핑을 딕셔너리에 저장합니다

result는 문자 조합들을 저장하는 결과 리스트입니다

if문에서는 입력 digits가 비어있는 예외 처리를 하여 빈 리스트를 반환합니다

dfs 함수에 필요한 매개변수는 입력 digits와 digits의 인덱스인데 이 변수는 제약조건 중 입력 digits의 길이와 조합되는 문자의 길이가 같아야 한다는 조건을 확인합니다.

이것은 현재 후보가 어떤 숫자에 해당하는 문자인지 알 수 있는 숫자입니다. 23이 입력되었다면 abc는 2에 해당하는 문자이기 때문에 인덱스가 1이고 def는 2입니다

dic은 위에서 선언한 디짓과 문자들의 매핑 딕셔너리이고 지금까지의 문자 조합과 결과 리스트를 매개변수로 사용합니다.

 

재귀 호출이 되는 순서는 다음과 같습니다.

dfs(‘23’, 0, dic, ’’ , result)

dfs(‘23’, 1, dic, ’a’ , result)

dfs(‘23’, 2, dic, ’ad’ , result)

dfs(‘23’, 2, dic, ’ae’ , result)

dfs(‘23’, 2, dic, ’af’ , result)

dfs(‘23’, 1, dic, ’b’ , result)

dfs(‘23’, 2, dic, ’bd’ , result)

dfs(‘23’, 2, dic, ’be’ , result)

dfs(‘23’, 2, dic, ’bf’ , result)

dfs(‘23’, 1, dic, ’c’ , result)

dfs(‘23’, 2, dic, ’cd’ , result)

dfs(‘23’, 2, dic, ’ce’ , result)

dfs(‘23’, 2, dic, ’cf’ , result)

 

 

 

Python으로 코드 작성

class Solution(object):
    def letterCombinations(self,digits):
        dictionary = { "2": "abc", "3": "def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}  
        result=[]
        if len(digits) ==0:
            return result
        self.dfs(digits, 0, dictionary, '',result)
        return result
    
    def dfs(self, nums, index, dictionary, path, result):
        if index ==len(nums):
            result.append(path)
            return
        letters =dictionary[nums[index]]
        for letter in letters:
            self.dfs(nums, index+1, dictionary, path + letter, result)