DFS/BFS_프로그래머스_단어 변환

https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

---

문제 접근

1. words에 target과 같은 단어가 없을 경우, target으로 변환 할 수 없으므로, 0을 반환
2. words.filter를 사용하여 begin으로부터 변환할 단어를 탐색.
   
   • 탐색 : func onlyOneTheSame을 사용. 
   • func onlyOneTheSame의 기능 : 두 단어를 글자 단위로 비교하여, 한 글자만 다를 경우 true를 반환
3. 재귀 탐색하여 나온 [Int?] 중 min값을 반환한다.

작성 중 수정한 내용

주석 처리 된 부분은 words에 target과 같은 element가 있는지 확인하는 내용이었으나, 완전히 불필요하므로, 이를 아래와 같이 수정했다.

        // var isImpossible = false
        
//         for (index,char) in target.enumerated() {
//             let ind = target.index(target.startIndex, offsetBy: index)
            
//             if words.first(where: {$0[ind] == char} ) == nil {
//                 isImpossible = true
//                 break
//             }
//         }
        
//         if isImpossible {
//             return sol
//         }
    
        guard let check = words.first(where: {$0 == target}) else {
            return sol
        }

 

정답 코드

import Foundation


func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
        var sol = 0
    
        guard let check = words.first(where: {$0 == target}) else {
            return sol
        }
        
        let result = recursion(start: begin, target: target, words: words)
        sol = result.compactMap({$0}).min()!
        
        return sol
    }
    
    func recursion(start: String, target: String, words: [String], did: Int = 0) -> [Int?] {
        var sol: [Int?] = []
        
        if start == target {
            sol.append(did)
            return sol
        }
        
        let next = words.filter({
            onlyOneNotTheSame(lhs: start, rhs: $0)
        })
        
        for element in next {
            var nextWords = words
            let idx = nextWords.firstIndex(where: {
                $0 == element
            })!
            nextWords.remove(at: idx)

            let result = recursion(start: element, target: target, words: nextWords, did: did + 1)
            
            sol.append(contentsOf: result)
        }
        
        return sol
    }
    
    func onlyOneNotTheSame(lhs: String, rhs: String) -> Bool {
        var count = 0
        
        for (index,char) in lhs.enumerated() {
            let ind = lhs.index(lhs.startIndex, offsetBy: index)
            if rhs[ind] == char {
                count += 1
            }
        }
        
        return count == lhs.count - 1 ? true : false
    }

 

사용된 testCase

"hit"	"hot"	["hot", "dot", "dog", "lot", "log"]	1
"1234567000"	"1234567899"	["1234567800", "1234567890", "1234567899"]	3
"hit"	"cog"	["cog", "log", "lot", "dog", "hot"]	4
"hit"	"cog"	["coh", "chg", "qog"]	0

 

여담

테스트케이스가 적어서 틀린 코드가 통과했다는 얘기가 있다.