[JS] 단어 변환

DFS를 활용하여 해결하였다.

 

 

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

프로그래머스

 

 

보통은 DFS/BFS를 통한 완전탐색 시에 배열을 많이 활용하는데 해당 문제의 경우 문자자체가 key가 되기 때문에 visited배열을 Map자료형을 사용하였다.

 

dfs를 활용해서 모든 경우의수를 탐색하며 최소값을 갱신시키면 된다.

 

 

function solution(begin, target, words) {
    
    //변할 수 있는 단어인지 체크
    const isCanChange = (st1,st2) => {
        let cnt = 0
        for (let i=0;i<st1.length;i++)
            if(st1[i]!==st2[i]) cnt ++
        return cnt===1 ? true : false
    }
       
    const visited = new Map()
    for (const word of words) visited.set(word,false)
    
    let ret = Infinity
    const dfs = (word,cnt) => {
        
        //종료조건
        if(word === target) {
            ret = Math.min(ret,cnt)
            return
        }
        
        for(const nxWord of words){
            if(!isCanChange(word,nxWord) || visited.get(nxWord)) continue
            visited.set(nxWord,true)
            dfs(nxWord,cnt+1)
            visited.set(nxWord,false)
        }
    }
    dfs(begin,0)
    return ret===Infinity ? 0 : ret
    
    
}