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

아래 프로그래머스 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

이 문제도 BFS(너비 우선 탐색)으로 직관적으로 풀 수 있다 !!

1. q에 begin 단어와 단계수인 0을 넣고 시작
2. visited 집합을 만들어 방문한 단어를 기록(중복 제거용)
3. q가 빌 때 까지 반복
   • 현재 단어(cur)와 단계수(step)을 꺼내기
   • 현재 단어가 target이라면 단계 반환
   • words 목록에서 한 글자만 다른 단어 중 아직 방문하지 않은 단어를 q에 step+1로 추가, visited에도 추가
4. 반복이 끝날 때 까지 target을 못찾았다면 0 반환

코드

---

1. Python

from collections import deque
def is_one_letter_diff(a, b):
    cnt = 0
    for x, y in zip(a, b):
        if x != y:
            cnt += 1
    return cnt == 1

def solution(begin, target, words):
    visited = set([begin])
    q = deque([[begin, 0]])
    
    while q:
        cur, step = q.popleft()
        if cur == target:
            return step
        for word in words:
            if is_one_letter_diff(word, cur) and word not in visited:
                visited.add(word)
                q.append([word, step+1])
    return 0

2. JS

function solution(begin, target, words){
    let head = 0;
    const q = [[begin, 0]];
    const visited = new Set([begin]);
    
    const isOneLetterDiff = (a, b) => {
        let cnt = 0;
        for(let i = 0 ; i < a.length ; i++){
            if(a[i] !== b[i]) cnt++;
        }
        return cnt === 1;
    }
    
    while(head < q.length){
        const [cur, step] = q[head++];
        
        if(cur === target) return step;
        
        for(const word of words){
            if(isOneLetterDiff(cur, word) && !visited.has(word)){
                visited.add(word);
                q.push([word, step + 1]);
            }
        }
    }
    
    return 0;
}

결과

---