(프로그래머스 JS)단어 변환

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

코딩테스트 연습 - 단어 변환

BFS 풀이.

 

countDiffer()함수.

인자로 받아온 word와 target의 다른 문자가 1개인지 확인하는 함수.

for문으로 word의 길이만큼 반복하면서,

문자가 몇개나 다른지 count로 확인한다.

만약 count === 1이라면 true를, 아니라면 false를 리턴한다.

 

solutino() 함수.

정답을 리턴할 answer,

BFS를 위한 큐 queue,

단어 중복 체크를 위한 map.

 

우선 queue에 시작하는 단어 begin을 넣어서 BFS를 진행한다.

 

가장 짧은 단어를 찾아야 하기 때문에 현재 queue의 length를 기억하고 진행해야 한다.

해당 size 만큼 사이클을 반복.

큐의 가장 앞에 있는 단어(현재 단어)를 currentWord에 저장.

만약 currentWord가 target과 같다면 answer을 리턴한다.

 

그렇지 않다면 큐를 pop 해주고 BFS 탐색을 진행한다.

for문으로 words의 length만큼 반복한다.

i번째에 해당하는 단어를 word라고 저장한다.

만약 currentWord와 word가 같다면 무시하고 다음 인덱스로 진행한다.

 

만약 map에서 currentWord + word나 word + currentWord에 해당하는 키가 없으며, 두 문자열의 다른 문자 갯수가 1이라면 큐에 넣어야 하는 조건에 해당한다.

map에 두 단어를 합친 문자열을 넣는 이유는 같은 조건을 반복하지 않기 위함이다.

for문은 0부터 진행하기 때문에 같은 조건으로 계속 바뀔 수 있으며, 이는 무한루프에 빠지게 된다.

이를 방지하기 위해 map에 두 단어를 합친 문자열(currentWord + word, word + currentWord)을 저장했다.

 

큐를 반복하면서 BFS 탐색을 진행하는데, 만약 큐가 비어있다면 단어를 target으로 바꿀 수 없기 때문에 0을 리턴한다.

const countDiffer = (word, target) => {
    let count = 0;
    
    for(let i = 0; i < word.length; i++){
        if(word[i] !== target[i]){
            count++;
        }
    }
    
    return count === 1 ? true : false;
}

const solution = (begin, target, words) => {
    let answer = 0;
    const queue = [];
    const map = new Map();
    
    queue.push(begin);
    
    while(queue.length){
        let size = queue.length;
        
        while(size--){
            const currentWord = queue[0];
            
            if(currentWord === target){
                return answer;
            }
            
            queue.shift();
            
            for(let i = 0; i < words.length; i++){
                const word = words[i];
                
                if(currentWord === word){
                    continue;
                }
                
                if(!map.get(currentWord + word) && !map.get(word + currentWord) && countDiffer(currentWord, word)){
                    queue.push(word);
                    map.set(currentWord + word, true);
                    map.set(word + currentWord, true);
                }
            }
        }
        
        answer++;
    }
    
    return 0;
}