Level3. 프로그래머스 단어 변환(BFS) - JavaScript

문제 설명

단어 A에서 다른 단어 B로 바꿀 때 가장 짧은 변환 과정을 찾아야 한다.

A가 바꿀 수 있는 단어는 words에 있는 단어로만 바꿀 수 있으며 한 번에 한개의 알파벳만 바꿀 수 있다.

에를 들어 hit에서 cog로 바꿔야 하고 words에는 [hot,dot,dog,lot,log,cog]가 들어 있다 했을 때

hit에서 알파벳 하나만 바꾸면 hot 으로 바꿀 수 있다.

hot는 dot 또는 lot으로 바꿀 수 있다.

다시 dot은 cog로 lot은 cog로 바꿀 수 있다. 

그렇다면 hit에서 cog로 4단계가 걸린다.

 

- 각 단어를 노드라고 봤을 때 한 노드와 다음 노드가 인접한지 여부는 단어 변환이 가능한지로 판별할 수 있다.

- 노드를 방문했다면 거리를 나타내는 값을 기록한다. hit - hot에서 hot의 경우 1 / hot - dot, hot - lot의 경우 dot과 lot은 2가 된다.

 

 

 

function solution(begin, target, words) {
    const visited = {}
    bfs(begin);
    return visited[target] === undefined ? 0 : visited[target];

    function bfs(node) {
        visited[node] = 0;
        const q = [node];
        
        while(q.length !== 0) {
            const currentNode = q.shift();
            words
            .filter(word => canChangeWord(word, currentNode))
            .forEach(movableNode => {
                if (visited[movableNode] === undefined) {
                    visited[movableNode] = visited[currentNode] + 1;
                    q.push(movableNode)
                }
            });
        }
    }
    
}

function canChangeWord (wordOne, wordTwo) {
    let count = 0;
    for (let i = 0; i < wordOne.length; i++) {
        if (wordOne[i] !== wordTwo[i]) count++;
    }
    
    return count === 1 ? true : false;
}