단어 변환

문제 설명

두 개의 단어 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 함수를 작성해주세요.

입출력

begin    target    words    return
"hit"    "cog"    ["hot", "dot", "dog", "lot", "log", "cog"]    4
"hit"    "cog"    ["hot", "dot", "dog", "lot", "log"]    0

문제 풀이

const solution = (begin, target, words) => {
  // 단어 체크용 함수
  const isSet = (a, b) => {
    let cnt = 0;
    // 만약 단어가 다르다면 개수 증가
    for (let i = 0; i < a.length; i++) {
      if (a[i] !== b[i]) {
        cnt++;
      }
    }
    // 다른 단어의 개수가 1개라면 true 아니라면 false 반환
    if (cnt === 1) return true;
    else return false;
  };
  // 중복 제거용 set
  let visited = new Set();
  const bfs = () => {
    visited.add(begin);
    let queue = [[begin, 0]];
    let head = 0;

    while (queue.length > head) {
      let [next, depth] = queue[head++];
      // 현재 단어가 target 이라면 depth 반환
      if (next === target) {
        return depth;
      }
      // 단어 배열 순회
      for (let word of words) {
        // 배열 내부 원소와 현재 단어가 한 단어 차이이고 방문 한 적이 없으면
        if (isSet(next, word) && !visited.has(word)) {
          // 방문 처리
          visited.add(word);
          // 다음 단어 탐색 및 depth 추가
          queue.push([word, depth + 1]);
        }
      }
    }
    return 0;
  };
  let result = bfs();
  return result;
};

아이디어 / 접근법

1. 두 단어 체크해서 단어 내부의 단어가 몇 개나 다른 지 체크
2. BFS, DFS 로 탐색 진행
3. 현재 단어가 target 이라면 depth 반환

후기

음 이게 프로그래머스 기준 LV3 문제였고 기존에 DFS 로 풀었던 적이 있어서 뭐 그렇게 어렵진 않았고 실제 문제를 푸는데도 한 30분 정도 쓴 것 같음!