[JS] 단어 변환

🔒 문제 (프로그래머스 DFS/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 합니다.

 

🌊 입출력

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

 

---

 

🔑 해결

🌌 알고리즘 - BFS

begin에서 target까지 변환할 수 있는 최단 경로의 거리를 구하는 문제와 같고, 변환 과정을 기억할 필요가 없으므로 DFS 보다 BFS를 사용한다.

큐를 이용하여 BFS를 구현하는데, 큐에 노드를 넣을 때 단어와 변경 횟수를 같이 넣어 최소 횟수를 구한다.

function solution(begin, target, words) {
    
    // 두 문자열을 비교하여 알파벳 하나만 다른지 검사하는 함수
    function isConvertible(from, to) {      
        let diff = 0;
        for(let i = 0 ; i < from.length; i++) {
            if(from[i] !== to[i])
                diff++;
        }
        
        return diff == 1;
    }
    
    let answer = 0;
    const q = [];
    const visited = Array(words.length);
    
    q.push([begin, 0]); // [시작 단어, 변경 횟수]를 루트 노드로 설정
    
    // BFS
    while(q.length) {
        // 큐에서 꺼낸 현재 노드의 [단어, 변경 횟수]를 활용할 수 있도록 설정 
        let [str, count] = q.shift();   
        
        // 현재 노드 방문 여부 체크
        visited.push(str);
        
        // 현재 노드의 단어가 target과 일치하면 변경 횟수 반환
        if(str === target)
            return count;
        
        // 방문하지 않았으며 변환 가능한 모든 노드를 큐에 넣어 다음 노드로 설정 
        words.forEach((word, index) => {
            if(!visited.includes(word) && isConvertible(str, word))     
                q.push([word, count+1]);    // 변경 횟수 같이 넣기
        });
    }
    
    return answer;
}