프로그래머스 dfs/bfs 단어변환

var answer = 0
    fun solution(begin: String, target: String, words: Array<String>): Int {
        val wordsArray = words.toMutableList()
        processing(begin,target,wordsArray,0)
        println(answer)
        return answer
    }

    fun processing(begin: String, target: String, words: MutableList<String>, count: Int) {
        if (begin == target) { // 종료
            if(answer ==0 || count<answer){
                answer = count
            }
            return
        } else {
            if(words.size == 0){ // 비었다
                return
            }else{
                for (i in words) {
                    if(begin.compareSolution(i)){// 바꿀수 있다
                        val wordsArray = words.toMutableList()
                        wordsArray.remove(i)
                        processing(i,target,wordsArray,count+1)
                    }
                }
            }
        }
    }

    fun String.compareSolution(Other: String): Boolean {
        var diffrentCount = 0
        this.indices.forEach {
            if (this[it] != Other[it]) {
                diffrentCount++
            }
        }
        return diffrentCount==1 // 1이면 true반환
    }

1)확장 함수를 사용해서 한글자만 다른가를 확인함.

2) 한글자만 다르다면 다른 와 바꾸면서 카운트를 늘려줌

3) 남은 글자가 없을때까지 타겟과 같지않으면 0 그대로 출력

4) 타겟과 같아진다면 지금 있는 카운트보다 낮으면 바꿈

 

 

다른 사람의 코드

import java.util.*

class Solution {
    fun String.diff(other:String):Int {
        return this.filterIndexed { index, c -> c != other.get(index) }.map { 1 }.sum()
    }

    class Word(val level:Int,val txt:String,val check:Array<Boolean>)

    fun solution(begin: String, target: String, words: Array<String>): Int {
        val q: Queue<Word> = LinkedList()
        val checkArray = Array(words.size) { false }
        q.add(Word(0,begin,checkArray))
        var ret = 0
        while(!q.isEmpty()) {
            val w = q.poll()
            if(w.txt == target) {
                ret = w.level
                break
            }
            w.check.forEachIndexed { index, b ->
                if(!b && (w.txt.diff(words[index]) == 1)) {
                    q.add(Word(w.level+1,words[index],w.check.clone().apply { set(index,true) }))
                }
            }
        }
        return ret
    }
}

이 분도 확장함수를 사용했구나. 근데 좀더 깔끔하네 ㅠㅠ

다른 글자와 비교해서 다른 글들을 이런식으로썻네

fun String.test(Other: String) : Int{
        return this.mapIndexed { index, c -> if(Other[index] != c) {1}else 0}.fold(0){
                acc, i -> acc+i
        }
    }

연습 삼아서 다르게도 만들어봄

 

위처럼 만들면 나처럼 모든 경우를 확인 안해도 되겠다. check를 통해서 글자를 맞추면 그 글자는 안맞춰도 되니까 저렇게 사용한듯 좋은듯.. 

 

그리고 더 많이 걸리는 케이스도 그까지 가기전에 걸려짐

 

 그니까 que에다가 확인해야되면서 조건에 맞는 케이스들을 넣고 하나씩 조건을 적용하면서 최적의 해를 구하는 방식인데 확실히 경우의 수도 줄어들고 효율적으로 문제를 풀 수 있다. 이런식으로 만들어야겠다.

 

※ 무조건 이런 풀이가 좋다는건 아닌거 같은게 만약에 정말 모든걸 다 확인해야되는 문제는 나처럼 하는게 나을 거 같고

중간 중간 조건에 의해서 확인을 할 필요가 없는 것은 위와같이 해결해야하는, 이번 조건을 만족했기에 다음 조건을 판단해야하는 이런문제에는 que에 넣어서 하나씩 해보는것이 좋을 것 같다.