[Programmers Lv.3 | JS] 단어 변환

프로그래머스 단어 변환 문제 링크

나의 풀이

function solution(begin, target, words) {
    const visited = [];
    let queue = [];
    
    // words에 target이 없으면 단어를 변환할 수 없다.
    if (!words.includes(target)) return 0;
    
    // begin(root)과 deps를 큐에 넣어준다.
    queue.push([begin, 0]);
    
    while (queue.length !== 0) {
        // 현재 단어와 deps를 꺼낸다.
        const [currentWord, deps] = queue.shift();
        
        // 현재 단어가 target과 일치하면 deps를 반환한다.
        if(currentWord === target) return deps;
        
        // 현재 단어와 words의 각 단어를 비교한다.
        words.forEach((word) => {
            if(isOneCharDifference(currentWord, word) && !visited.includes(word)) {
                visited.push(word); // 방문 처리
                queue.push([word, deps + 1]); // 단어와 deps를 queue에 넣어준다.
            }
        })
    }
    
    // words를 전부 순회 했는데도 단어를 변환할 수 없다면 0 반환한다.
    return 0;
}

// 한 번에 한 개의 알파벳만 바꿀 수 있는지 확인
const isOneCharDifference = (word1, word2) => {
    let count = 0;
    
    for(let i = 0; i < word1.length; i++) {
        if(word1[i] !== word2[i]) count++;
    }

    return count === 1 ? true : false;
}

문제를 풀면서

BFS(Breadth-First Search)

• 너비 우선 탐색으로 루트 노드에서 시작하여 인접한 노드부터 탐색하는 알고리즘

• queue를 이용

• 탐색 수행 시 O(n)의 시간 복잡도

• 최단거리를 구하는 문제에서 이용
  ⇒ begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾는 문제이므로 BFS 적용

• 노드 탐색 순서

  • 루트 노드를 queue에 넣고 방문 처리 한다.
  • queue에서 노드를 꺼내고, 해당 노드와 인접한 노드 중 방문하지 않은 노드를 모두 queue에 넣고 방문 처리 한다.
  • 두 번째 과정을 더 이상 수행할 수 없을 때까지 반복한다.

• 예제

  const bfs = (graph, start, visited) => {
    const q = [];
    q.push(start);
    visited[start] = true;
  
    while (q.length !== 0) {
      const v = q.shift();
      console.log(v);
  
      for(const cur of graph[v]){
        if(!visited[cur]){
          q.push(cur);
          visited[cur] = true;
        }
      }
    }
  }
  
  const graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7],
  ]
  
  const visited = [...Array(9).fill(false)];
  
  bfs(graph, 1, visited);

한 번에 한 개의 알파벳만 바꿀 수 있습니다.

• 아래와 같이 단어를 한글자씩 자르는 방법을 생각함

  const sliceWord = (word, index) => {
      const wordToArray = word.split('');
      return wordToArray.slice(index, index + 1).join('');
  }

• 이 후 단어의 각 글자를 비교하는 과정과, 한 번에 한 개의 알파벳만 바꿀 수 있는지 확인하는 과정에서 막힘

• 다른 풀이들을 참고함

  const isOneCharDifference = (word1, word2) => {
      let count = 0;
  
      for(let i = 0; i < word1.length; i++) {
          // 두 단어의 각 인덱스의 글자를 비교하여 다르다면 count에 1을 더한다.
          if(word1[i] !== word2[i]) count++;
      }
      // 한 번에 한 개의 알파벳만 바꿀 수 있으므로 count가 1이 아닐 경우 false를 반환한다.
      return count === 1 ? true : false;
  }

⇒ 해당 문제는 BFS의 기본 틀에 문제의 조건만 추가하면 풀 수 있는 문제이다.

다른 풀이를 보면서

• 방문 처리(visited)를 배열로 하지 않고 Set 객체를 이용하여 구현하는 방법도 있다.

마무리

• BFS의 개념은 이해하지만 코드로 그려지지 않는다.
• 코드를 많이 작성해보면서 익숙해지면 되겠징
• 코테 공부 어렵지만 스터디 참여하면서 주에 한 문제라도 제대로 이해해보자는 심정으로 참여했는데, 스터디원들의 설명을 말로 들으니 조금 더 이해가 되는 것 같다.
• 코테 공부하면서 알고리즘 내용 정리 해야징

참고

• [JS] BFS, DFS
• [Javascript로 정리하는 이코테] 4. DFS/BFS
• [javascript] 프로그래머스 단어 변환 (DFS/BFS)