[ JavaScript ] 프로그래머스 level3 43163번 단어 변환

1. 단어 변환 #43163

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

      

      

      

    
    

      <code />
    
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 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예begintargetwordsreturn

"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

2. 나의 풀이 

      

      

      

    
    

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

  words.push(begin);
  const size = words.length;
  const length = begin.length; // 각 단어들의 길이
  const counting = Array(size).fill(0); // 방문 배열 겸, 지금까지 몇 번 교체를 하였는지 저장하는 배열

  const arr = Array.from(Array(size), () => Array()); // 연결관계를 나타내는 배열 (인접리스트)

  /* 인접리스트 생성하기 */
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      let count = 0;
      for (let k = 0; k < length; k++) {
        if (i !== j && words[j] !== begin && words[i][k] === words[j][k])
          count++;
      }
      if (count === length - 1) {
        arr[i].push(words[j]);
      }
    }
  }
  /* 위 코드를 실행한 뒤 arr은 아래와 같다. 
    [
      [ 'dot', 'lot' ],
      [ 'hot', 'dog', 'lot' ],
      [ 'dot', 'log', 'cog' ],
      [ 'hot', 'dot', 'log' ],
      [ 'dog', 'lot', 'cog' ],
      [ 'dog', 'log' ],
      [ 'hot' ]
    ]
  */

  const queue = [begin];

  while (true) {
    if (queue.length === 0) break;
    const curWord = queue.shift();
    if (curWord === target) break;
    const linked = arr[words.indexOf(curWord)];

    for (const word of linked) {
      const cnt = counting[words.indexOf(curWord)];
      if (counting[words.indexOf(word)] === 0) {
        counting[words.indexOf(word)] = cnt + 1;
        queue.push(word);
      }
    }
  }

  /*
    위 코드를 실행하고 난 뒤 counting 배열은 아래와 같다.
    [ 1, 2, 3, 2, 3, 4, 0 ]
    위 배열의 인덱스는 words 배열의 인덱스와 매칭된다.
    각 숫자의 뜻은 "hit" 부터 시작하여 각 단어까지 몇번의 교체가 이루어졌는지를 의미한다. 
    ex) hit -> dot 이 되려면 2번의 교체가 이루어져야 함 
  */
  return counting[words.indexOf(target)];
}

 

• BFS 개념을 공부하면서, 인접리스트를 이용해서 푼 문제가 생각나서 처음부터 접근을 그런 식으로 했던 것 같다. 
• 그래서 너무 비효율적인 코드(무려 3중for문. ... )임을 알지만, 너비 우선 탐색을 하기 전에, 인접리스트를 만들어서 해결하고자 했다. 
• begin도 비교하여 인접리스트에 반영하기 위해 begin words에 추가하여 같이 비교를 해주었다.
• 그리고 counting 배열은 visited 배열 겸, 지금까지 몇번 교체를 했는지 저장해주는 배열로 활용했다. 
• 그러고나서 BFS를 돌려주었다. 

3. 다른 풀이를 참고하여 수정한 풀이

      

      

      

    
    

      <javascript />
    
function solution(begin, target, words) {
  // 다른 사람의 풀이를 참고한 풀이
  // 연결리스트 따로 만들지 않고, isAvailable 함수를 두어 두 단어가 교체 가능한지 여부를 판단

  if (!words.includes(target)) return 0;
  const counting = Array(words.length).fill(0); // 방문 배열 겸, 지금까지 몇 번 교체를 하였는지 저장하는 배열
  const queue = [begin];

  while (true) {
    if (queue.length === 0) break;
    const curWord = queue.shift();

    if (curWord === target) break;

    const cnt = counting[words.indexOf(curWord)] ?? 0;

    for (let i = 0; i < words.length; i++) {
      if (isAvailable(curWord, words[i]) && counting[i] === 0) {
        counting[i] = cnt + 1;
        queue.push(words[i]);
      }
    }
  }
  // 두 단어가 교체 가능한 단어인지 비교해서 리턴하는 함수
  function isAvailable(standard, compare) {
    let differntCount = 0; // 다른 문자의 수, 1보다 크면 두 단어는 교체 불가
    for (let i = 0; i < standard.length; i++) {
      if (standard[i] !== compare[i]) differntCount++;
      if (differntCount > 1) return false;
    }
    return true;
  }

  return counting[words.indexOf(target)];
}

• 인접리스트에만 포커스를 맞추고 있어서 다른 방식이 안떠올랐었는데, 위 코드처럼 두 단어를 비교하는 함수를 따로 정의하여 T/F 값만 비교하니까 훨씬 깔끔하고 효율적인 코드가 되었다 ! 
• 나머지 코드는 비슷하게 풀었다. 

입력값의 크기가 커질수록 차이가 많이 나는 듯 하다.