깊이-너비 우선 탐색 / 3 / 단어 변환 (JS) bfs

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여

begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

 

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면

"hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

 

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐

begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

 

문제 풀이 방법

• 우선 가장 짧은 변환 과정을 구한다는 것을 보고 DFS보다는 BFS가 문제 풀이에 좋다고 생각했다.
• 단어를 넣을 큐와 방문한 노드를 기록할 배열을 만들어준다.
• 우선 제한 사항에 target이 없다면 0을 반환하는 코드를 작성한다.
• while문으로 묶은 뒤 que에 저장된 정보를 해체배열로 가져온다.
• words를 forEach로 각 단어 마다 기존의 단어와 다른 문자의 갯수를 파악
• 이후 1개만 다른 단어들만 저장 후 다시 시작하여 if문으로 target과 같은 단어를 받았다면 return 해준다.

 

주의 사항

1. DFS와 BFS의 사용처를 잘 파악하고, 넓게 탐색한다는 것을 잘 익혀야 겠다.

 

코드

function solution(begin, target, words) {
    let answer = 0;
    let que = [];
    let visited = [];
    
    if(!words.includes(target)) return 0;
    
    que.push([begin, answer]);
    
    while(que.length){
        let [v, c] = que.shift();
        
        if(v === target){
            return c;
        }
        words.forEach(word => {
            let notMatch = 0;
            
            if(visited.includes(word))
                return;
            
            for(let i=0; i<word.length; i++){
                if(word[i] !== v[i])
                    notMatch++;
            }
            
            if(notMatch === 1){
                que.push([word, ++c]);
                visited.push(word);
            }
        })
    }
    return answer;
}