단어 변환 - Kotlin (DFS)

프로그래머스

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

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

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

 

나의 풀이

이 문제는 간단한 DFS 문제이다. 이 문제에서는 2가지를 수행하면 된다.

 

1. 바꿀 단어 선택
2. 바꿀 단어가 한 개의 알바벳만 다른지

이 2개를 수행하면 쉽게 해결할 수 있다. 시간을 줄이기 위해 visited를 통해 중복을 체크해줘 한번 바꾼 단어는 다시 바꾸지 않게 해 주었다.

 

class Solution {
    var answer = 0
    fun solution(begin: String, target: String, words: Array<String>): Int {
        dfs(begin, target, 0, words, BooleanArray(words.size))
        return answer
    }
    
    fun dfs(start: String, target: String, depth: Int, words: Array<String>, visited: BooleanArray) {
        if (start == target) {
            answer = depth
            return
        }
        
        for (i in words.indices) {
            if (!visited[i] && check(start, words[i])) {
                visited[i] = true
                dfs(words[i], target, depth + 1, words, visited)
                visited[i] = false
            }
        }
    }
    
    fun check(a: String, b: String): Boolean {
        var cnt = 0
        for (i in 0 until a.length) {
            if (a[i] != b[i]) cnt++
        }
        
        return if (cnt == 1) true
        else false
    }
}