[프로그래머스 Lv.3] 단어 변환

◼️ 문제

단어 변환

1. 문제 설명

2. 제한사항

3. 입출력

◼️ 풀이

✏️ 전반적인 풀이과정

가장 짧은 단계의 변환을 찾아야 한다 => 전형적인 BFS 방식이다.

1. words 배열에 target이 존재하지 않으면 변환이 불가능 하므로 0을 반환한다.
2. BFS 순회를 위해 방문해야 할 단어를 저장하는 need_visited 배열, 방문한 단어를 기록하는 visited 객체를 생성한다.
3. begin부터 시작해야 하므로, need_visited에 begin을 넣고, visitied에 0번째 순서로 방문했다는 기록을 남긴다.
4. need_visited 배열에 아무것도 없을 때까지 target을 찾는다.
   4-1. 현재 방문한 단어를 알기 위해 need_visited의 첫번째 요소를 꺼낸다.
   4-2. 만약 현재 단어가 target과 같다면 현재 단계를 결과로 반환한다.
   4-3. target이 아니라면, words를 하나씩 확인하며 다음 단계로 넘어갈 수 있는 단어를 찾는다. 찾은 단어가 방문하지 않았던 단어라면, need_visited 배열에 추가하고 몇 단계에 방문했는지와 함께 방문 기록을 visited 객체에 기록한다.
5. need_visited 배열에 아무것도 없을 때까지 변환을 했음에도 target에 도달할 수 없다면 0을 반환한다.

📃 풀이과정 상세 설명

target이 words에 없는 경우

단어를 계속 변환할 때 words 배열에 있는 단어로 변경해주면서 최종적으로 target을 만들어야 하기 때문에 words에 target이 없다면 무의미한 탐색이다.

// target이 words에 없다 === 변환이 불가능하다.
if (!words.includes(target)) return 0;

따라서 제일 초반에 target이 words에 없는 경우에는 결과를 바로 리턴해주도록 한다.

BFS를 위한 need_visited, visited 세팅

const need_visited = []; // 방문해야 할 단어를 기록하는 배열 (큐)
const visited = {}; // 방문한 단어를 기록하는 객체

BFS를 구현하기 위해 가장 필수적인 세팅이라고 볼 수 있다.

need_visitied는 앞으로 방문해야 할 단어를 넣어두는 대기실의 개념이다.
방문해야 할 단어들은 push를 통해 뒤에 차곡차곡 쌓이게 될텐데 BFS의 개념은 너비우선탐색이기 때문에 넣어둔 단어는 앞에서부터 꺼내주어야 한다. 따라서 큐의 형식으로 사용할 예정이다.

visitied는 방문한 단어를 기록하는 객체이다. visitied는 배열이든, 객체든, Map이든, Set이든 각자 원하는대로 만들면 되는데, 나는 가장 익숙하고, 방문 여부를 기록함과 동시에 몇단계에서 방문한 단어인지 함께 기록하기 위해 객체를 택했다.

begin 부터 시작

need_visited.push(begin);
visited[begin] = 0;

begin부터 시작해야 하므로, 방문해야 할 요소로 need_visited 배열에 넣어준다.
그리고 정확히는 아직 방문하지 않았지만, need_visited 배열에 넣은 순간 방문은 확정된 것이나 다름없기 때문에 visitied에도 함께 기록한다.

begin에서 시작하는 건 아직 변환이 시작된 건 아니기에 0단계로 기록해준다.

isNext 함수 구현

본격적으로 BFS 탐색을 하기 전에 필요한 함수를 먼저 구현했다.

function isNext(word, target) {
  let count = 0;

  for (let i = 0; i < word.length; i++) {
    if (word[i] !== target[i]) {
      count++;
      if (count > 1) return false;
    }
  }

  return count === 1;
}

이 함수는 현재 단어인 word가 target으로 변경이 가능한지 확인하는 함수이다.
단어 길이가 동일하다는 건 문제에서 보장해주었으니, 길이 걱정은 하지 않고 철자 하나하나를 비교하면 된다.

철자가 2개 이상 다르다면 바로 변환이 불가능하다는 의미의 false를 리턴한다.
모든 철자를 확인했을 때, 철자가 다른 개수가 1개라면 변환이 가능하다는 의미의 true를,
철자가 모두 동일하다면 변환이 불가능 하다는 false를 리턴한다.

여기서 문제에 words에는 중복되는 단어가 없다고 해주었기 때문에 count가 0인 경우도 고려를 해야하나 싶지만, begin이 words에 없다는 보장은 없기 때문에 필요하다!
(이 부분을 고려하지 않아서 처음 제출할 땐 틀렸다..)

BFS 탐색 시작

while (need_visited.length > 0) {
  // 현재 단어 꺼내기
  const current = need_visited.shift();

  // 현재 단어가 target이라면 바로 결과 리턴
  if (current === target) return visited[target];

  // 현재 단어가 target이 아니라면 변환 가능한 단어 검색
  words.forEach((word) => {
    if (isNext(current, word) && !visited[word]) {
      need_visited.push(word);
      visited[word] = visited[current] + 1;
    }
  });
}

방문해야 할 단어가 없을 때까지 계속 target을 찾으면 된다.

현재 단어를 알아야 하므로 need_visited의 첫번째 요소를 꺼내, target과 일치하는지 확인한다. 만약 target이 맞다면, 이미 visited에 몇단계인지 기록을 했을테니 결과를 리턴해주면 된다.

target이 아니라면 현재 단어를 기준으로 변환 가능한 단어를 찾아야 하기 때문에, words 배열을 순회하며 isNext 함수로 변환 가능 여부를 확인한다.
특정 단어로 변환이 가능하다는 것을 확인했다면 그 단어가 이미 방문한(혹은 방문할) 단어인지도 확인해야 한다. (확인할 거 투성이네;;)

만약 이미 방문 기록이 있다면 패스.
아직 방문하지 않은 단어라면 need_visited에 넣어주고, 방문하게 될 단계와 함께 방문 기록을 visitied에 남겨준다.

이걸 target을 찾을 때까지 혹은 need_visited가 빌 때까지 반복하면 된다. need_visited에 아무것도 없을 때까지 확인했음에도 target을 못찾았다면 변환이 불가능한 케이스이므로 0을 반환한다.

💻 코드

function solution(begin, target, words) {
  if (!words.includes(target)) return 0;

  const need_visited = [];
  const visited = {};

  need_visited.push(begin);
  visited[begin] = 0;

  while (need_visited.length > 0) {
    const current = need_visited.shift();

    if (current === target) return visited[target];

    words.forEach((word) => {
      if (isNext(current, word) && !visited[word]) {
        need_visited.push(word);
        visited[word] = visited[current] + 1;
      }
    });
  }

  return 0;
}

function isNext(word, target) {
  let count = 0;

  for (let i = 0; i < word.length; i++) {
    if (word[i] !== target[i]) {
      count++;
      if (count > 1) return false;
    }
  }

  return count === 1;
}