[리트코드 17] DFS 탐색 문제풀이2

DFS 탐색(깊이 우선 탐색) 알고리즘은 대표적인 그래프 탐색 방법 중 하나로 모든 노드를 방문(전체 탐색)해야하는 경우 BFS(너비 우선 탐색)에 비해 간단하게 풀이가 가능하여 선호되는 방식이다. 아래 문제의 경우도 모든 번호의 조합을 찾아야 함으로 DFS 방법으로 풀이할 예정이다.

 

17. 전화 번호 문자 조합 (Letter Combinations of a Phone Number)

Example

주어진 2~9 사이의 숫자를 포함하는 문자열의 숫자가 나타낼 수 있는 가능한 모든 문자 조합을 출력하라. (단, 1은 어떤 문자도 매핑되어있지 않다.) 예를 들어 "23" 의 입력값이 주어졌을 때 2는 abc 의 문자 출력이 가능하고 3은 def 문자 출력이 가능하므로 각각 한 문자씩 조합을 해보면 총 9개의 문자로 조합이 가능하다.

각 자릿수에 해당하는 키판 배열

Constraints

-  0 <= digits.length <= 4

- digits[i] 은 2~9 사이의 값이다.

Solution

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

 

입력값(digits) 이 위와 같이 주어졌을때, 키판 배열(keypad) 에서 입력값을 쪼개어 각각 숫자에 해당하는 문자열을 반복하면서 조합해나간다. dfs() 함수는 문자 조합(letter_combinations) 이 입력값의 자릿수와 동일해질 때까지 재귀문을 돌며 자릿수와 동일해졌을때 결과를 추출하고 빠져나온다. 이렇게 모든 경우의 수를 DFS로 탐색하고 조건이 충족되었을때 함수를 빠져나온다.

코드 샘플

# python
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def dfs(index, letter_combinations):
            # 입력값 길이 만큼 문자 조합 후 리턴
            if len(letter_combinations) == len(digits):
                answer.append(letter_combinations)
                return

            # 입력값 길이 만큼 반복
            for i in range(index, len(digits)):
                for letter in keypad[digits[i]]:
                    dfs(i + 1, letter_combinations + letter)
        
        # 입력값이 "" 인 경우
        if not digits:
            return []
        
        answer = []
        keypad = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        dfs(0, "")
        
        return answer

 

로그를 찍어서 확인하면 단계별로 재귀문이 어떻게 동작하는지 확인하기 쉽다.

===============
i=0, l=a >> a
i=1, l=d >> ad
i=1, l=e >> ae
i=1, l=f >> af
----------------
i=0, l=b >> b
i=1, l=d >> bd
i=1, l=e >> be
i=1, l=f >> bf
----------------
i=0, l=c >> c
i=1, l=d >> cd
i=1, l=e >> ce
i=1, l=f >> cf
================
i=1, l=d >> d
i=1, l=e >> e
i=1, l=f >> f

answer=['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

 

참조: 파이썬 알고리즘 인터뷰 https://github.com/onlybooks/algorithm-interview