[프로그래머스] 단어 변환 (43163)(Kotlin)

원본 문제

문제 설명

두 개의 단어 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 함수를 작성해주세요.

제한 사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

예제 입출력

begin	target	words	return
“hit”	“cog”	[“hot”,”dot”,”dog”,”lot”,”log”,”cog”]	4
“hit”	“cog”	[“hot”,”dot”,”dog”,”lot”,”log”]	0
“hit”	“hhh”	[“hhh”,”hht”]	2
“hit”	“wow”	[“hot”,”dog”,”dot”,”wow”]	0
“hot”	“dog”	[“hot”,”dog”]	0

문제 풀이1

//import java.util.Stack

class Solution {
    var check: BooleanArray = booleanArrayOf()
    val list: MutableList<Int> = mutableListOf()
    // var stack: Stack<String> = Stack()

    fun solution(begin: String, target: String, word: Array<String>): Int {
        return if (word.contains(target)) {
            for (i in word.indices) {
                check = BooleanArray(word.size) { false }
                if (isConvertable(begin, word[i])) {
                    check[i] = true
    //                stack.push(begin); stack.push(word[i])
                    dfs(word[i], target, word, 1)
    //                stack.pop(); stack.pop()
                }
            }
            if (list.isEmpty()) 0
            else {
                list.forEach { println(it) }
                list.min()!!
            }
        }
        else 0
    }

    fun dfs(begin: String, target: String, word: Array<String>, count: Int) {
        if (begin == target) {
            list.add(count)
    //        println(stack.joinToString(" -> ", "", "(${count})"))
            return
        }

        for (i in word.indices) {
            if (check[i]) continue
            if (isConvertable(begin, word[i])) {
                check[i] = true
    //            stack.push(word[i])
                dfs(word[i], target, word, count + 1)
    //            stack.pop()
                check[i] = false
            }
        }
    }

    // fun isConvertable(begin: String, target: String): Boolean = begin.filter { target.contains(it) }.count() == begin.length - 1
    // begin의 각 Character를 target이 가지고 있는지 파악하여 변환 가능한 글자를 찾아내려 했지만
    // 이렇게 탐색을 할 경우 hht(begin)-> hih(target)가 가능하여 문제가 있음
    // i는 index라고 했을 때, begin[i] == target[i]로 탐색을 해야 올바른 방법

    fun isConvertable(begin: String, target: String): Boolean = BooleanArray(begin.length) { begin[it] == target[it] }.count { it } == begin.length - 1

}

문제 풀이1 해설

저는 DFS를 이용해 풀었습니다.

1. word에 target이 없을 경우 0을 리턴
   2-1. word에 target이 있을 경우 DFS 탐색 시작
   2-2. begin에서 target으로 가는 모든 방법을 찾아 카운트하여 list에 add함
   3. DFS탐색 종료 후, list를 확인
   3-1. list가 비어 있는 경우(target이 word에 존재하지만, word내에서 target으로 가는 방법이 없을 경우) 0 리턴
   3-2. list가 비어 있지 않는 경우, list.min()으로 list의 최솟값을 반환 이러한 로직으로 풀이했을 때, 테스트케이스3가 틀렸는데

isConvertable함수에서 현재 String에서 이동할 String으로 이동할 수 있는지 판별하는 방식이 잘못돼서 문제가 발생했습니다.

기존에 했던 방식은 현재 String의 각 글자를 이동할 String이 포함하고 있는지 확인하는 방식으로 진행했는데, 이럴 경우 hht -> hih로 가는 경우가 생깁니다.

(문제의 조건에서 한 글자만 변경하여 이동가능하다 했지만, 이 경우는 2글자가 변경되었는데도 이동함)

이런 접근 방식에서 현재 String과 이동할 String의 같은 index 글자를 비교 하는 방식으로 해결했습니다.