[프로그래머스 kotlin] 단어변환

문제

 

시작 단어와 완성단어가 주어지고 시작단어를 최소한으로 변환시켜 완성단어까지 바꾸는 문제이다.

단 단어의 변환시 한 글자만 다른 단어로 변환할 수 있다.

---

풀이

먼저 단어를 변환시키는 방법으로 DFS를 사용하였다.

또한 단어의 한글자만 다른 것을 검사하는 check 함수를 구현하였다.

 

먼저 Check함수이다.

 fun check(a: String, b: String): Boolean {
    var cnt = 0
    for (i in 0 until a.length) {
        if (a[i] != b[i]) cnt++
    }
    if (cnt == 1) return true
    else return false
}

두 단어를 불러와서 검사한 뒤 한글자만 다를경우 True를 반환한다.

 

fun DFS(start: String, depth: Int) {
    if (start == target) {
        answer = min(answer, depth)
        return
    }

    for (i in words.indices) {
        if (!visited[i] && check(start, words[i])) {
            visited[i] = true
            DFS(words[i], depth + 1)
            visited[i] = false

        }
    }
}

DFS는 다음과 같다.

단어가 마지막 단어와 일치할경우 현재 answer를 갱신해준다.

아닐경우 단어목록을 불러와서 방문하지 않고 check함수를 통과했을경우 다음 depth로 넘겨준다.

 

answer의 갱신을 할 때 현재 depth와 비교하여 작은값으로 갱신하므로 가장 짧은 변환을 찾을 수 있다.

 

---

코드

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