[Algorithm] 단어변환

📋 문제 

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

 

제한 사항

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

 

입출력 예

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

 

✏️ 풀이

제한 사항을 보았을 때, 단어의 개수가 50개를 넘지 않고 단어의 길이가 10이하였기 때문에 DFS로 풀어도 괜찮을 것이라 생각했다. 

이미 방문한 곳을 처리할 때에는 배열을 자르고 이어붙이기 보다는 단어의 길이가 무조건 3이상이므로 ''로 빈 문자열로 변환한 뒤에 반복문 내에서 빈 문자열일때 continue를 이용하여 넘겨주면 되겠다는 생각을 했다. 

 

단어를 하나씩 변경할 수 있기 때문에 현재 단어와 target 단어 사이의 알파벳 차이 개수를 확인해야 하는데 split과 reduce를 사용하여 확인했다. 이때 차이나는 알파벳 개수의 수가 1인 경우 현재 문자를 변경하고 words 배열에서 해당 단어를 빈 문자열로 변경한 뒤에 현재 단어와 새로운 단어배열, cnt를 넘겨주며 재귀로 돌려줬다. 

 

dfs 함수 초기에는 현재 단어와 target 단어를 확인하여 같다면 현재 cnt를 answer와 비교하여 answer를 최신화 시켜주었다.

또한, 단어 배열에 target이 없는 경우 변환할 수 없는 상황이기 때문에 solution 함수 내 처음에 filter를 사용하여 확인하고 포함되지 않는 경우에 0을 반환했다.

 

⌨️ 코드

function solution(begin, target, words) {
  var answer = Infinity;

  const validation = words.filter(word => word === target);
  if (!validation.length) return 0;

  const dfs = (now, words, cnt) => {
    if (target === now) {
      answer = Math.min(answer, cnt);
      return;
    }

    for (let i = 0; i < words.length; i++) {
      const word = words[i];
      if (!word) continue;

      const diffCnt = word.split('').reduce((n, w, i) => n + (w === now[i] ? 0 : 1), 0);
      if (diffCnt === 1) {
        const nextWords = [...words];
        nextWords[i] = '';
        dfs(word, nextWords, cnt + 1);
      }
    }
  };

  dfs(begin, words, 0);

  return answer;
}

console.log(solution('hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog']));