고득점 Kit [DFS/BFS] - 단어 변환

문제

풀이

전형적인 BFS를 활용하는 문제, 처음엔 객체를 활용할까 하다가 좋은 예시가 있어 참고해서 풀었다. 한 가지 주목할 점은 한 개 차이가 난다는 것에 주목하여서 다음 queue에 넣어주는 로직이 참신하다.

function solution(begin, target, words) {
    // 한 개씩 고쳐서 결국 정답에 도달하는 것이니까 다른 게 1개인 애들을 큐에 계속 넣어주면 됨
    let ans = 0;
    let visited = [];
    let queue = [];
    
    // words가 target을 갖고 있지 않으면 횟수는 0
    if (!words.includes(target)) return 0
    
    // count를 할 값과 시작값을 보내줌
    queue.push([begin, ans])
    
    while (queue.length) {
        let [v, ans] = queue.shift()
        
        // 꺼내온 값이 ans값과 같다면, 여태까지 증가시킨 ans를 return
        if (v === target) {
            return ans
        }
        
        words.forEach(word => {
            let notEqual = 0;
            
            // 이미 다녀온 애가 있으면 넘어감
            if (visited.includes(word)) return
            
            // 큐에서 나온 애를 갖고 반복문을 돌며 같지 않은 갯수를 셈
            for (let i=0; i<word.length; i++) {
                if (v[i] !== word[i]) notEqual++
            }
            
            // 한 개 차이가 난다는 것은 다음 순번으로 들어갈 차례
            if (notEqual === 1) {
                ans++
                queue.push([word, ans])
                visited.push(word)
            }
        })
        
    }
    
    return ans
    
    
}