[BFS] 프로그래머스 '단어 변환' - js

1. 문제

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

프로그래머스

2. 코드

이 문제는 최소 단계를 반환하는 문제이기도 하고, 이미 방문한 단어는 또 방문할 필요가 없기 때문에 BFS로 풀어야 한다.

어떻게 해야 최소 단계를 반환할 수 있느냐?!
큐를 사용한다 => 단어 한 개만 다른 경우 큐에 넣는다 => 큐에 들어간 순서대로 처리 되므로 최소 단계 반환 가능!

여기선 선 증감 후 할당이 되는 ++cnt가 핵심이다. cnt++로 바꾸면 선 할당 후 증감이 되기 때문에 최종적인 answer이 우리가 원하는 형태로 나오지 않는다.

https://dojang.io/mod/page/view.php?id=96 

C 언어 코딩 도장: 13.4 증감 연산자의 위치에 따른 차이점 알아보기

정상적인 로직을 실행하면 이렇게 나온다.

방문 여부를 저장해주는 이유는 forEach 문에서 앞에서 이미 방문한 단어들에 대해 처리해줄 필요가 없기 때문이다. 

만약 큐에서 꺼낸 값이 ['log',4]일 때 forEach 문 안에서 앞에서 방문한 hot, dot, dog등을 다시 방문해줄 필요가 없고, 'log' 뒤에 있는 'cog'와도 한 자리 밖에 차이가 나지 않기 때문에 큐에 넣어주고 싶지만 이미 'cog'는 'dog' 방문시 큐에 넣어졌고, 큐에 넣어져봤자 cnt 부분이 5가 되어 의미가 없다.

이 코드에서 각 단어의 방문 여부를 저장하는 visited 배열을 평소처럼 new Array로 만들면 queue에 push하는 배열에 그 단어의 index까지 포함해야 해당 요소의 visited 값을 1 또는 true로 변경할 수 있으므로, 여기서는 방문한 단어 자체를 visited 배열에 push 하는 편이 낫다.

function solution(begin, target, words) {
    let visited = [];
    let queue = [];
    // 예외처리
    if(!words.includes(target)) return 0;
    
    queue.push([begin,0]);
    
    while(queue.length){
        let [word, cnt] = queue.shift();
        if(word === target) return cnt;
        // 단어 목록 중 word와 한 글자만 차이나는 단어를 큐에 넣는다.
        words.map((el) => {
                let diff = 0;
                
                for(let i=0;i<el.length;i++){
                    if(el[i] != word[i]) diff++;
                }
                
                if(diff === 1){
                    queue.push([el,cnt+1]);
                    visited.push(el);
                } 
            })
    }
 
}

다른 코드

function solution(begin, target, words) {
    // 최소 단계니까 bfs
    // 단어 visited 배열 필수
    // 현재 단어와 한 개의 알파벳만 다른 경우 queue에 push
    // queue [단어, cnt]
    let answer = 0;
    let visited = new Array(words.length).fill(0);
    let queue = [[begin,0]];
    
    while(queue.length){
        let cur = queue.shift();
        if(cur[0] === target){
            answer = cur[1];
            break;
        }else{
            for(let i=0;i<words.length;i++){
                let diff = 0;
                for(let j=0;j<words[i].length;j++){
                    if(words[i][j] !== cur[0][j]) diff++;
                }
                if(diff === 1 && !visited[i]) {
                    queue.push([words[i],cur[1]+1]);
                    visited[i] = 1;
                }
            }
        }
    }
    
    return answer;
}

 

복기

3/31
4/14