[Level 3 / BFS] 단어 변환 + Swift

단어 변환

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

문제 유형

문제 유형은 너비 우선 탐색이다. begin과 연결된(한글자만 다른) 단어를 찾고, 그 단어에서 다시 연결된 단어를 찾아 찾아 target에 도달하는 단계를 도출하는 문제이다. 최소 몇 단계를 거치는지를 return 하라는 말에서도 유추할 수 있다.

let begin = "hit"
let target = "cog"
let words = ["hot", "dot", "dog", "lot", "log", "cog"]

나의 풀이

isSimilar 함수

두 단어를 받아 한글자만 다른지 Bool타입으로 알려주는 함수이다.

func isSimilar(_ strA: String, _ strB: String) -> Bool {
    let strAArr = strA.map({ $0 })
    let strBArr = strB.map({ $0 })
    var result = 0
    for (index, char) in strAArr.enumerated() {
        if char != strBArr[index] { result += 1 }
    }
    return result == 1
}

solution 함수

처음에 words에 target이 없다면 0을 반환한다.

bfs함수를 돌린다. 이 함수의 인자로는 현재 단어를 뜻하는 currentWord, 횟수를 세는 count, 그리고 방문했는지를 저장하는 visited 배열이 있다. 만약 result가 0 이상이지만 count가 더 크다면 함수를 끝낸다. 그렇지 않다면 words에서 현재 단어와 비슷하면서 방문하지 않은 단어를 찾는다. target과 같다면 result와 count를 비교하여 최소값을 저장한다. 그렇지 않다면 visited배열에서 방문한 배열의 인덱스의 위치에 해당하는 값을 true로 변경한다. 다시 답을 찾기 위해 함수를 돌린다.

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    if words.firstIndex(of: target) == nil { return 0 }
    var result = 0
    
    func bfs(currentWord: String, count: Int, visited: [Bool]) {
        if result > 0 && count >= result { return }
        
        for (index, word) in words.enumerated() {
            if isSimilar(currentWord, word) && !visited[index] {
                if word == target {
                    if result == 0 || count < result {
                        result = count + 1
                        break
                    }
                }
                var newVisited = visited
                newVisited[index] = true
                bfs(currentWord: word, count: count + 1, visited: newVisited)
            }
        }
    }
    
    bfs(currentWord: begin, count: 0, visited: Array(repeating: false, count: words.count))
    return result
}