[프로그래머스] 단어 변환

문제 정보

• 프로그래머스 문제 링크
• 난이도 : level 3

 

해결 방법

노드 사이에서 관계를 가지고 있으므로 자료 구조는 그래프를 사용하고 탐색하는 방법은 BFS 혹은 DFS 를 사용하여 풀 수 있습니다. 해당 문제에서는 단어를 변환할 수 있는 최소 단계를 구해야 하므로 BFS 를 사용합니다. DFS 를 사용할 경우 최소 단계를 발견하더라도 다른 경로를 모두 탐색해야 최소 단계임을 보장할 수 있기 때문에 비효율적이기 때문 입니다. 

 

소스 코드

function solution(begin, target, words) {
    let answer = 0;
    

    // target 이 words 에 없는 경우
    if(!words.includes(target)){
        return answer;
    }

    // 방문여부 초기화
    const visited = new Array(words.length);
    visited.fill(false);
    
    const queue = [];
    let tempAnswer = 0;
    let nexts = []; // 더 깊은 단계의 노드 배열
    const bfs = function(begin, target, words){
        queue.push(begin);

        while(0 < queue.length){
            const word = queue.shift();
            
            if(words.includes(word)){
                visited[words.indexOf(word)] = true;
            }

            if(word === target){
                answer = tempAnswer;
                break;
            }

            for(let idx = 0; idx < words.length; idx++){
                if(isChange(word, words[idx]) && !visited[idx]){
                    nexts.push(words[idx]);
                }
            }

            if(queue.length < 1){
                //console.log(`nexts:${nexts}`);
                tempAnswer++;
                queue.push(...nexts);
                nexts = [];
            }
        }
    };

    bfs(begin, target, words);
    
    return answer;
}

// 한개의 알파벳만 차이나는지 여부
function isChange(word1, word2){
    let result = false;
    let diff = 0;

    for(let idx = 0; idx < word1.length; idx++){
        if(word1[idx] !== word2[idx]){
            diff++;
        }
    }
    if(diff === 1){
        result = true;
    }

    return result;
}

 

개선점

• 변환하지 못했을 경우 0 을 반환해야 하기 때문에 예외처리를 해주었는데 불필요하게 탐색하는 경우가 줄긴 하지만 변환하지 못하는 경우를 모두 판단하지는 못합니다.
• queue 에 다음 탐색할 단어들을 넣는 과정에서 방문하지 않은 (visited 값이 true 가 아닌) 노드는 조건에서 제외하지만 이미 queue 에 들어가 있는 노드들은 넣을 필요가 없으니 빼는 것이 좋아 보입니다.

 

참고 자료

• [프로그래머스] 단어 변환(Level 3, JAVA, 왜 BFS를 사용해야 하나?, BFS/DFS, 깊이 탐색, 너비 탐색)
• [javascript] 프로그래머스 단어 변환 (DFS/BFS)