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
'algorithm > problem solving' 카테고리의 다른 글
[리트코드 94, 144, 145] 이진 트리 순회(binary tree traversal) (0) | 2022.01.18 |
---|---|
[리트코드 46] DFS를 활용한 순열 문제풀이 (0) | 2022.01.14 |
[리트코드 200] DFS 탐색 문제풀이1 (0) | 2022.01.11 |
[리트코드 15] 투 포인터(Two Pointers) 를 활용한 문제풀이3 (0) | 2022.01.06 |
[리트코드 42] 투 포인터(Two Pointers) 를 활용한 문제풀이2 (0) | 2022.01.05 |