Skip to main content

작성일 : 2024.11.16

단어 변환 문제

문제 설명​

시작 단어(begin)를 목표 단어(target)로 변환하는데 필요한 최소 단계를 찾는 문제입니다.

변환 규칙​

  1. 한 번에 한 글자만 변경 가능
  2. words 배열에 있는 단어로만 변환 가능

예시​

begin: "hit"
target: "cog"
words: ["hot","dot","dog","lot","log","cog"]

변환 과정: "hit" -> "hot" -> "dot" -> "dog" -> "cog"
답: 4 (4단계)

제한 조건​

  1. 단어 제한

    • 알파벳 소문자로만 구성
    • 길이: 3 ≤ 길이 ≤ 10
    • 모든 단어의 길이는 동일

  2. words 배열

    • 크기: 3 ≤ 크기 ≤ 50
    • 중복 단어 없음

해결 코드 (DFS 방식)​

function solution(begin, target, words) {
  if (!words.includes(target)) return 0;
  let answers = [];

  const dfs = (word, index, level, visit) => {
    if (index >= words.length) return;
    for (let i = 0; i < word.length; i++) {
      const letter = sliceWord(word, i);
      const temp = words.filter(
        (v) => !visit.has(v) && sliceWord(v, i) === letter
      );
      if (temp.includes(target)) {
        answers.push(level + 1);
        return;
      }
      temp.map((v, i) => {
        const visited = new Set([...visit]);
        visited.add(v);
        dfs(v, i, level + 1, visited);
      });
    }
  };

  const sliceWord = (word, i) => {
    let wordArr = word.split("");
    wordArr.splice(i, 1);
    return wordArr.join("");
  };

  dfs(begin, 0, 0, new Set());
  return answers.length < 1 ? 0 : Math.min(...answers);
}

해결 코드 (BFS 방식)​

function solution(begin, target, words) {
  if (!words.includes(target)) return 0;
  let answer = 0;
  let temp = [];
  const visited = new Set();
  const queue = [];
  queue.push(begin);

  while (queue.length) {
    const word = queue.shift();
    visited.add(word);
    if (word === target) {
      return answer;
    }
    for (let i = 0; i < word.length; i++) {
      const letter = sliceWord(word, i);
      const matched = words.filter(
        (v) => !visited.has(v) && sliceWord(v, i) === letter
      );
      temp.push(...matched);
    }

    if (queue.length < 1) {
      answer++;
      queue.push(...temp);
      temp = [];
    }
  }

  return answer;
}

알고리즘 설명​

DFS 방식​

  1. 각 단계에서 한 글자씩 변경 가능한 모든 단어 탐색
  2. 방문 처리를 통해 중복 방문 방지
  3. 목표 단어 도달 시 현재까지의 단계 수 저장
  4. 모든 경로 탐색 후 최소값 반환

BFS 방식​

  1. 큐를 사용하여 현재 단계에서 가능한 모든 변환 탐색
  2. 각 레벨별로 단계 수 증가
  3. 목표 단어 도달 시 현재 단계 수 반환
  4. 더 이상 변환이 불가능할 때까지 반복

주요 메서드 설명​

  1. Set 객체 활용
const visited = new Set(); // 방문 처리
visited.add(word); // 방문 표시
!visited.has(word); // 미방문 확인
  1. 배열 메서드
words.filter(); // 조건에 맞는 단어 필터링
queue.shift(); // 큐에서 단어 추출
temp.push(); // 임시 배열에 단어 추가

시간 복잡도​

  • DFS: O(n _ m _ l), n은 단어 수, m은 단어 길이, l은 가능한 경로 수
  • BFS: O(n * m), n은 단어 수, m은 단어 길이

공간 복잡도​

  • O(n): n은 words 배열의 크기