Lv.3 - 단어 변환

풀이 원리 : BFS

• 만약 words 목록에 target이 없으면 바로 0 return
• 두 단어가 한 글자만 차이나는지 체크하는 함수 check 작성
• queue의 첫 시작 root값은 begin

BFS 작성 요령

• queue가 빌 때까지 or 원하는 값이 나올 때까지 반복
• while문을 반복할 때마다 queue의 크기를 기억
• 그 크기만큼 for문을 돌린다.

function solution(begin, target, words) {
  if (!words.includes(target)) return 0;

  const checkWord = (w1, w2, len, cnt) => {
    for (let i = 0; i < len; i++) {
      if (w1[i] !== w2[i]) cnt++;
      if (cnt > 1) return false;
    }
    return true;
  };

  let answer = 0;
  const len = target.length;
  const Q = [begin];

  while (Q.length) {
    const size = Q.length;
    for (let i = 0; i < size; i++) {
      const v = Q.shift();
      if (v === target) return answer;
      for (const w of words) {
        if (checkWord(w, v, len, 0)) Q.push(w);
      }
    }
    answer++;
  }
}

1. 단어 [l1, l2...], length : n이 주어졌을 때 한 글자만 다른 단어 목록 [w1, w2, w3..., v1, v2, v3...], length : m을 찾아서 queue에 등록한다.
2. n만큼 순회를 했으면 for문이 끝나고 다음 while문을 실행한다.
3. 단어 [w1, w2, w3..., v1, v2, v3...]과 한 글자만 차이나는 목록 [x1,x2,...y1,y2,...]를 queue에 등록한다.

• 주의점 : [x1, x2, ... , y1, y2 ...]에서는 이전에 검사했던 [l1, l2...]도 다시 들어간다. 검사할 양이 많으면 중복 검사도 그만큼 커진다.