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

문제 풀이 아이디어

주어진 배열에서 begin에서 변형할 수 있는 단어를 찾아서 변형하고 다시 변형된 단어에서 변형할 수 있는 단어를 찾아서 변형하는 과정을 반복해야 합니다. 이 과정에서 특별한 패턴이 없고 배열 안의 단어들을 전부 일일히 대조해야 하므로 완전 탐색 알고리즘을 사용해야 합니다.

완전 탐색을 통해서 begin에서 target으로 가는 루트를 거리를 기록해가면서 탐색합니다.

최단거리 알고리즘의 관점에서 bfs를 사용해도 되고 dfs를 통해 모든 루트를 탐색해서 최솟값을 구해도 됩니다. 여기서는 dfs를 통해 풀어보겠습니다.

코드

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    // from에서 to로 변환할 수 있는 글자인지 확인하는 함수
        //🚫 처음에 여기 차집합으로 했다가 틀림 (동일한 알파벳이 동일한 '위치'에 있어야 하므로 순서가 중요함)
        // + Array로 바꾸니까 실행속도도 엄청 빨라짐
    func isChangeable(_ from: String, _ to: String) -> Bool {
        
        var difference = from.count
        // String은 subscript로 접근할 수 없으니 Array로 형변환
        let from = Array(from)
        let to = Array(to)
        
        // 한글자씩 비교
        for i in 0..<from.count {
            if from[i] == to[i] { difference -= 1 }
        }
        
        // 차이가 1이면 true
        return difference == 1 ? true : false
    }
    
    // dfs 구현
    func dfs(_ now: String, _ depth: Int) {
        // 탈출조건: now가 target과 동일하면
        if now == target {
            ans = min(depth, ans) //👉 현재까지의 변환횟수를 ans와 비교해서 최솟값 저장
            return
        }
        
        // 모든 words를 순환하면서 미방문 + 변환가능한 단어에서 dfs 실행
        for i in 0..<words.count {
            if !visited[i] && isChangeable(now, words[i]) {
                visited[i] = true
                dfs(words[i], depth + 1)
                visited[i] = false
            }
        }
    }
    
    var ans = Int.max
    var visited = Array(repeating: false, count: words.count)
    
    // target이 words에 없으면 return 0
    guard words.contains(target) else { return 0 }
    
    dfs(begin, 0)
    
    return ans
}