단어 변환

프로그래머스 Level 3

📚 문제 설명

두 개의 단어 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

입출력 예 #1

문제에 나온 예와 같습니다.

입출력 예 #2

target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

📝 작성 코드

function solution(begin, target, words) {
    let queue = [[begin, 0]];
    let visit = new Set();
    
    while (queue.length > 0) {
        let [current, step] = queue.shift();
        
        if (current === target) return step;
        
        for (const word of words) {
            if (!visit.has(word) && convert(current, word)) {
                visit.add(word);
                queue.push([word, step + 1]);
            }
        }
    }
        
    return 0;
}

function convert(a, b) {
    let diff = 0
    for (let i = 0; i < a.length; i++) {
        if (a[i] !== b[i]) diff++;
        if (diff > 1) return false;
    }
    
    return diff === 1;
}

너비 우선 탐색을 위해 사용할 변수 queue를 생성한다. [현재 단어, 변환 횟수] 형태로 저장될 수 있도록 초기에는 [begin, 0]을 넣는다. 또한 중복 방문을 피하기 위해 방문한 단어를 기록하는 Set visit을 생성한다.

while문을 활용하여 queue가 비어 있을 때까지 반복문을 계속 진행한다. queue에서 하나의 값을 꺼낸 뒤, current와 step에 할당한다. 만약 current와 target이 같다면 step을 반환한다.

convert(a, b) 함수를 생성하여 단어 a와 b의 각 문자를 비교하고, 다른 문자의 개수가 1개면 true, 그 외의 경우에는 false를 반환한다.

for문을 활용하여 words 배열을 순회하며 word 변수를 방문하지 않았고, 단어의 변환이 가능하다면 해당 단어를 queue에 넣고, step을 1 증가시키면서 방문한 것으로 기록한다.

만약 queue를 전부 탐색해도 target이 될 수 없다면 0을 반환한다.

⏰ 걸린 시간

테스트 1 〉 통과 (0.09ms, 33.4MB) 테스트 2 〉 통과 (0.24ms, 33.5MB) 테스트 3 〉 통과 (0.30ms, 33.5MB) 테스트 4 〉 통과 (0.10ms, 33.4MB) 테스트 5 〉 통과 (0.09ms, 33.5MB)