[Javascript] 프로그래머스 - 단어 변환

문제 설명

주어진 단어 begin을 target으로 변환하는 가장 짧은 과정을 찾는 문제입니다. 변환 규칙은 다음과 같습니다.

1. 한 번에 한 개의 알파벳만 변경할 수 있습니다.
2. 변경 후의 단어는 words 리스트에 포함되어 있어야 합니다.

변환할 수 없는 경우에는 0을 반환합니다.

---

제한 사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 모든 단어의 길이는 3 이상 10 이하이며 동일합니다.
• words 리스트에는 3개 이상 50개 이하의 단어가 있으며 중복이 없습니다.
• begin과 target은 같지 않습니다.

---

해결 방법

• 알고리즘: BFS (너비 우선 탐색)
• 풀이 방법:
  1. Queue를 사용하여 BFS 탐색을 수행합니다.
  2. begin 단어를 시작점으로 큐에 추가하고, 방문 여부를 체크합니다.
  3. 큐에서 단어를 꺼내며, 한 글자만 차이나는 단어를 찾아 큐에 추가합니다.
  4. target 단어에 도달하면 변환 횟수를 반환합니다.
  5. 모든 탐색이 끝날 때까지 target에 도달하지 못하면 0을 반환합니다.

---

시간 복잡도

• O(N^2 * M) (N: 단어 개수, M: 단어 길이)
• 단어마다 모든 단어를 비교하며 한 글자 차이 여부를 확인하므로 O(N * M), 이를 BFS 탐색으로 처리하여 최악의 경우 O(N^2 * M)이 됩니다.

---

구현 코드

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  enqueue(value) {
    const node = new Node(value);

    if (this.size === 0) {
      this.front = node;
      this.rear = node;
    } else {
      this.rear.next = node;
      this.rear = node;
    }

    ++this.size;
  }

  dequeue() {
    if (this.size === 0) {
      return null;
    }

    const value = this.front.value;
    this.front = this.front.next;
    --this.size;

    if (this.size === 0) {
      this.rear = null;
    }

    return value;
  }
}

function solution(begin, target, words) {
  const size = begin.length;
  let answer = 0;
  let q = new Queue();
  let visit = new Set();

  q.enqueue([begin, 0]);

  while (q.size > 0) {
    const [curWord, count] = q.dequeue();

    for (const word of words) {
      if (visit.has(word)) continue;

      let diff = 0;
      for (let i = 0; i < size; ++i) {
        if (curWord[i] !== word[i]) ++diff;
        if (diff > 1) break;
      }

      if (diff === 1) {
        if (word === target) return count + 1;

        visit.add(word, count + 1);
        q.enqueue([word, count + 1]);
      }
    }
  }

  return answer;
}