[swift] 단어 변환

📌 프로그래머스 Lv - 3

💪 작심삼일도 삼일에 한번씩하면 꾸준히..!

📝 KeyWord

⇢ BFS / DFS : [너비 우선 탐색, 깊이 우선탐색]
⇢ String

DFS와 BFS중, 어떤 방식으로 풀어도 해결할 수 있지만, DFS 재귀함수 구현을 Swift로 한번 시도해보고자 DFS, 재귀함수 방식으로 풀이하였다!

📌 문제풀이

---

⇢ 해당 단어가 다른 단어로 변환될 수 있는지 확인하는 방법은?
⇢ DFS를 통해, 목표 단어까지 최소 횟수를 얻는 방법은?

먼저 단어 변환을 위해서, 해당 단어가 다음 단어로 변환이 가능한지 확인해야한다.
(1) Comp1, Comp2와 같이 두 단어를 String으로 전달 받는다.
(2) String을 Char단위로 비교하기위해, "map"을 활용한다
(3) map을 통해, 두 단어의 요소를 배열로 만든 후, 요소별 비교를 진행.
(4) 서로 다른 요소의 개수가 1개라면 변환 가능한 단어

그 다음으로, DFS를 통해 시작 단어에서 부터 목표 단어까지 완전탐색을 진행한다.
(1) DFS (시작단어, 목표 단어, 단어 목록
       -> cycle을 통해 DFS 진행
(2) 목표 단어로 변환됬을 경우, answer에 최소값인 경우 기록.
(3) 모든 탐색을 종료한 후에, answer 리턴.

(1) 시작 조건문, 변환 하고자 하는 목표 단어가 words 목록에 있는지 확인
   (1-1) 있다면, DFS를 통해 탐색하며, 최소 횟수 기록
   (1-2) 없다면, 0을 리턴

📝 전체코드

---

import Foundation

func isConvert(_ to: String, _ from: String) -> Bool {
    var isToConvertFrom: Int = 0
    let comp1 = to.map{ $0 }
    let comp2 = from.map{ $0 }
    for i in 0..<comp1.count{
        if comp1[i] != comp2[i] { isToConvertFrom += 1 }
    }
    return isToConvertFrom == 1
}

func DFS(_ begin: String, _ target: String, _ words: [String]) -> Int{
    
    var answer:Int = Int.max
    var visit:[Bool] = Array(repeating: false, count: words.count)
    func cycle(_ word:String , _ depth: Int){
        if word == target{
            answer = answer > depth ? depth : answer
            return
            
        }
        for i in 0..<words.count{
            if !visit[i] && isConvert(word, words[i])
            {
                visit[i] = true
                cycle(words[i], depth + 1)
                visit[i] = false
            }
        }
    }
    cycle(begin, 0)
    return answer
    
}

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    
    var answer = 0
    if words.contains(target) { answer = DFS(begin, target, words) }
    return answer
}