[알고리즘] 깊이/너비 우선 탐색(DFS/BFS) / 단어 변환

https://programmers.co.kr/learn/courses/30/lessons/43163?language=kotlin 

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

 

해당 알고리즘은 제한 조건에 신경쓰면 쉽게 풀 수 있는 문제다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

위 내용을 잘 체크하고, isValid 함수를 생성해 유망한지 체크 후 유망하다면 다음 DFS 재귀를 호출하면 된다.

var minStepCount = 0
 
fun main() {
    val begin = "hit"
    val target = "cog"
    val words = arrayOf("hot", "dot", "dog", "lot", "log", "cog")
    val visited = Array(words.size) { false }
 
    minStepCount = words.size
 
    if (!listOf(*words).contains(target)) {
        return
    } else {
        dfs(begin, target, words, visited, 0)
    }
 
    println(minStepCount)
}
 
fun dfs(begin: String, target: String, words: Array<String>, visited: Array<Boolean>, step: Int) {
    if (begin == target) {
        minStepCount = step.coerceAtMost(minStepCount)
    }
    for (i in words.indices) {
        if (visited[i]) continue
        if (isValid(begin, words[i])) {
            visited[i] = true
            dfs(words[i], target, words, visited, step + 1)
            visited[i] = false
        }
    }
}
 
/**
 * currStr => hit
 * word => hot
 * 한글자만 같을경우 단어 변환이 가능하기 때문에 TRUE!(조건사항)
 */
fun isValid(begin: String, word: String): Boolean {
    var sameCount = 0
    for (i in begin.indices) {
        if (begin[i] == word[i]) {
            sameCount++
        }
    }
    return sameCount == begin.length - 1
}
 

29번째 Line에서 visited(방문여부) 를 다시 false로 돌리는 이유는 dfs가 끝나고 나서 이전 Node로 돌아와 다음 Node로 진입해야하는데 visited가 true라면 더 검색하지 못하기 때문이다.

 

위 소스에는 빠져있는데 12번째 line에 return 0 하면 된다.