[Programmers] 단어 변환


  • 프로그래머스 단언 변환 문제 풀이입니다.

const bfs = (begin, target, words) => {
  let dist = { [begin]: 0 }; // 각 단어로 변경되는데 몇회가 걸려는지
  let visited = []; // 이미 변환된 단어 기록하는 배열
  let stack = [begin];

  while (stack.length) {
    const currentWord = stack.shift();

    for (let i = 0; i < words.length; i++) {
      // 아직 선택되지 않은 단어
      if (!visited.includes(words[i])) {
        let count = 0;
        // 비슷한 문자 몇개인지 확인
        for (let j = 0; j < currentWord.length; j++) {
          // 비교하는 단어의 문자가 같은 경우
          if (currentWord[j] === words[i][j]) {
            count += 1;
          }
        }

        // 문자 1개 빼고 다 비슷한 경우
        if (count === currentWord.length - 1) {
          // 현재 단어로 변환되는데 걸린 횟수 +1
          dist[words[i]] = dist[currentWord] + 1;

          // 해당 단어가 target과 같은 경우
          if (words[i] === target) {
            return dist[words[i]];
          }

          visited.push(words[i]);
          stack.push(words[i]);
        }
      }
    }
  }
};

function solution(begin, target, words) {
  let visited = [];
  const result = bfs(begin, target, words);
  return result ? result : 0;
}

Reference









© 2020. by dkmqflx

Powered by dkmqflx