프로그래머스 알고리즘(단어변환)

프로그래머스 알고리즘(단어변환)

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=javascript

DFS

function solution(begin, target, words) {
  const existTarget = words.includes(target);
  if (!existTarget) {
    return 0;
  }
  const beginLength = begin.length;
  const array = [];
  const dfs = (changeNum, word, extraArray) => {
    if (word === target) {
      array.push(changeNum);
      return 0;
    }
    if (extraArray.length <= 0) {
      return 0;
    }
    for (let i = 0; i < beginLength; i++) {
      const removeCurWord = word.slice(0, i) + word.slice(i + 1);
      extraArray.forEach((extra) => {
        const removeIndexExtra = extra.slice(0, i) + extra.slice(i + 1);
        const sameStr = removeCurWord === removeIndexExtra;
        if (sameStr) {
          const filter = extraArray.filter((f) => f !== extra);
          dfs(changeNum + 1, extra, filter);
        }
      });
    }
    return 0;
  };
  dfs(0, begin, words);
  array.sort((a, b) => a - b);
  return array[0] || 0;
}

BFS

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

  const queue = [{ word: begin, depth: 0 }];

  while (queue.length > 0) {
    const { word, depth } = queue.shift();

    if (word === target) {
      return depth;
    }

    for (let i = 0; i < words.length; i++) {
      if (isTransformable(word, words[i])) {
        queue.push({ word: words[i], depth: depth + 1 });
        words.splice(i, 1);
        i--;
      }
    }
  }

  return 0;
}

function isTransformable(word1, word2) {
  let diffCount = 0;
  for (let i = 0; i < word1.length; i++) {
    if (word1[i] !== word2[i]) {
      diffCount++;
      if (diffCount > 1) return false;
    }
  }
  return diffCount === 1;
}

후기

이번 문제는 단어를 한글자를 변환하여 target을 만드는 가장 빠른 방법을 구하는 문제인데, 처음에 잘몰라서 DFS로 풀었고 풀고나서 다른 사람들의 풀이를 보니 BFS로 풀어버리면 성능, 가독성이 더 좋다는걸 느낀 문제였다.