플랫폼 | 번호 | 제목 | 유형 | 난이도 | 언어 |
---|---|---|---|---|---|
프로그래머스 | 84512 | 모음 사전 | 완전탐색 | Lv.2 | Swift, Python |
이 문제는 완전탐색 문제로 백트래킹(BackTracking)으로 해결할 수 있다. 물론 이외의 방법으로도 문제를 해결할 수 있다.
백트래킹의 핵심은 완전탐색 중에 한정 조건에 부합하지 않으면 이전으로 돌아가 다음 것을 탐색하는 것이다. DFS나 BFS와 함께 구현할 수 있다.
A부터 UUUUU까지 DFS로 탐색하면서 count를 세고, 찾고자 하는 단어에 도달하면 탐색을 멈추도록 했다. 탐색 과정 중에는 백트래킹 기법을 사용하여 찾고자 하는 단어가 아니거나 5자리이면 이전 노드로 돌아가도록 했다.
import Foundation
func solution(_ word:String) -> Int {
let charList = ["A", "E", "I", "O", "U"]
var count = 0
func bt(_ result: String) -> Bool {
count += 1
if result == word {
return true
}
if result.count == 5 {
return false
}
for char in charList {
if bt(result + char) {
return true
}
}
return false
}
for char in charList {
if bt(char) {
return count
}
}
return 0
}
def solution(word):
charList = ["A", "E", "I", "O", "U"]
count = 0
def bt(result):
nonlocal count
count += 1
if result == word:
return True
if len(result) == 5:
return False
for char in charList:
if bt(result + char):
return True
for char in charList:
if bt(char):
return count
기존에 DFS나 BFS 문제는 경험해 보았지만 이를 활용한 백트래킹 문제는 처음 접하였다. 그래서 아직 익숙하지 않아 더 많은 문제를 풀어볼 필요가 있을 것 같다.