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

 

🔥문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

🔥풀이

일단 스펠링이 하나만 다른 경우만 단어 변환이 가능하므로 이동가능한 word인지를 확인 하는 함수 can_convert를 정의하여 이를 이용했다. 그리고 재귀함수의 방법을 통해 tagert으로 이동 가능한 모든 경우의수를 깊이우선탐색 방식으로 탐색하면서 목표로한 target 문자열로 변경이 됐을 경우를 포착하고 몇번이동했는지를 현재 최솟값과 비교하여 더 작게 이동했다면 최솟값을 update하는 방식을 이용했다.

 

🔥풀이

function solution(begin, target, words) {
    
    // 애초에 답이 words 에 없을 때
    if(!words.includes(target)) return 0

    
    const can_convert =(orgin_word,next_word)=>{
        // 중복되는 seplling이 있을 수 있음        
        const origin_word_arr =[...orgin_word]
        const compare_arr = [...next_word]
        
        let diff_count = 0
        for(let i=0; i<=origin_word_arr.length-1; ++i){
            if(origin_word_arr[i]!==compare_arr[i]){
                ++diff_count
            }
        }
        
        return diff_count === 1 ? true : false
    }

    
    let min = 100;

    const dfs=(now_word,rest_words,count)=>{
        if(now_word===target){
            
            min = Math.min(min,count)
            return
        }
        rest_words.forEach((word,i,self)=>{
            if(can_convert(now_word,word)){
                let copied = [...self]
                copied.splice(i,1)
                dfs(word,copied,count+1)
            }
        })
    }
    dfs(begin,[...words],0)
    
    
    return min===100 ? 0 : min;
}