프로그래머스 - 단어 변환 (JavaScript)

생각해보기

처음에는 아스키 코드를 통해 a ~ z까지 다 바꾸면서 비교하는 방식으로 했었다.

그러나 문제 조건을 활용하면 연산 횟수를 줄일 수 있다.

 

조건 1 - words라는 배열 안에 있는 단어로만 변환 가능하다는 점

조건 2 - 한 번의 변환 과정에서 하나의 알파벳만 바꿀 수 있다는 점

 

다른 알파벳의 수를 count해서 count가 1이면 변환 가능한 단어임을 알 수 있다.

조건 1에 의해 words 배열 안에 있는 단어들에 한정하여 비교를 진행하면 된다.

 

DFS를 통해 탐색할 때, visited를 초기화하여 다른 경우의 수에 대해서도 탐색을 가능하게 한다.

또한 count를 갱신하면서 최소 횟수를 찾는다.

 

풀이)

function solution(begin, target, words) {
  let answer = 0;
  let visited = Array.from({ length: words.length }, () => false);

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

  function bfs() {
    let count = 0;
    let queue = [[begin, 0]];
    while (queue.length) {
      let [word, count] = queue.shift();
      if (word == target) {
        return count;
      }
      for (let i = 0; i < words.length; i++) {
        if (visited[i] == false && checkDiff(word, words[i])) {
          visited[i] = true;
          queue.push([words[i], count + 1]);
        }
      }
    }
    return 0;
  }
  answer = bfs();

  return answer;

  //   // DFS
  //   let INF = 1e9;
  //   let min = INF;

  //   function dfs(word, count) {
  //     if (word == target) {
  //       min = Math.min(min, count);
  //       return;
  //     }
  //     for (let i = 0; i < words.length; i++) {
  //       if (visited[i] == false && checkDiff(word, words[i])) {
  //         visited[i] = true;
  //         dfs(words[i], count + 1);
  //         visited[i] = false;
  //       }
  //     }
  //   }

  //   dfs(begin, 0);

  //   if (min == INF) {
  //     min = 0;
  //   }

  //   return min;
}