[Programmers] 단어 변환

문제

 

깊이/너비 우선 탐색(DFS/BFS) > 단어 변환

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

 

 

아이디어

 

이번 문제의 아이디어는 BFS입니다.

 

DFS를 이용해도 풀릴지는 정확히 모르겠지만 DFS보단 BFS를 사용하는 게 더 효율적으로 풀릴 수 있는 문제입니다.

 

풀이법은 다음과 같습니다.

 

1. 시작단어를 queue에 담기

2. queue에 담긴 단어와 words에 있는 단어를 비교하여 변환이 가능한지 확인

3. 변환이 가능하고 words에 속하는 단어로 더 빠르게 변환이 가능하면 queue에 저장

4. queue가 비워질 때까지 2~3을 반복

 

 

구현 코드 (JavaScript)

 

class Node {
    constructor(count, word) {
        this.count = count;
        this.word = word;
    }
}

function solution(begin, target, words) {
    const visited = new Array(words.length).fill(Number.MAX_VALUE); // 몇 번만에 words로 변경가능한지를 저장
    const queue = [];
    let res = Number.MAX_VALUE; // 변환할 수 있는 최소값
    queue.push(new Node(0, begin));
    
    while(queue.length != 0) {
        const node = queue.shift();
        
        if(node.word === target) { // 타겟단어가 되었을 경우
            res = Math.min(res, node.count);
            continue;
        }
        
        for(let i=0; i<words.length; i++) {
            const word = words[i];
            
            let count = 0;
            for(let j=0; j<word.length; j++) { // 문자열 비교
                if(node.word[j] === word[j]) {
                    count++;
                }
            }
            
            if(count === word.length-1 && node.count+1 < visited[i]) { // 알파벳 한 개만 다르고 i번째 인덱스의 단어로 더 빠르게 변환이 가능한 경우
                visited[i] = node.count+1;
                queue.push(new Node(node.count+1, word));
            }
        }
    }
    
    return res === Number.MAX_VALUE ? 0 : res;
}

 

 

 

읽어주셔서 감사합니다.