프로그래머스 단어 변환 풀이

• 지난 글에서 프로그래머스 문제도 많이 풀어봐야 겠다고 다짐했었는데, 오늘에서야 건드려보기 시작했다(^^...

---

문제 풀이 - 프로그래머스 단어 변환

  DFS/BFS 문제. 단어 배열이 주어지고 시작 단어와 타겟 단어가 주어지면 시작 단어를 단어 배열 내에 주어진 단어로 차례차례 바꿔가며 타겟 단어를 만드는 것이 문제의 목표이다. 문제에서 주어지는 조건은 다음과 같다.

 

• 시작 단어에서 시작하여 주어진 단어 배열 내의 단어로 단어를 바꿔가며 타겟 단어를 만들어야 한다.
• 이 때, 글자를 한 글자만 바꿀 수 있다. 즉 다음 단어로 고를 수 있는 단어는 바꾸기 전 단어와 '딱 한 글자만 차이나는 단어'이다.
  • ex) lot에서 get(2글자가 차이난다)으로의 변환은 불가능하지만, let으로의 변환은 가능하다.
• 변환을 완료하였다면 변환까지 걸리는 최소 단계를 출력한다. 변환이 불가능하다면 0을 출력한다.
• 최종적으로 만들어야 하는 타겟 단어를 포함해 바뀌는 모든 단어들은 단어 배열 내에 존재해야 한다.
  • 타겟 단어가 단어 배열 내에 존재하지 않으면, 만들 수 없는 경우이므로 0을 출력해야 한다.

 

  문제를 보니 DFS나 BFS 어느 쪽을 사용해도 해결 가능할 것처럼 보였는데, 이번엔 DFS를 사용해서 문제를 해결하기로 하였다. 문제 풀이에는 아래와 같은 점들을 고려했다.

 

• 변환할 다음 단어를 고르기 위해, 변환이 가능한지의 여부를 반환하는 isChangeable 이라는 함수를 만든다.
• 문제의 요건은 변환까지 걸리는 '최소 단계'를 구하는 것이므로, 일반적인 DFS문제처럼 방문여부 배열(visited)을 boolean으로 관리하는 것이 아닌, 이 단어로 시작 단어를 변환하는데 걸리는 최소 단계를 기록한다.
  • 이렇게 하면 탐색을 진행하다 이미 변환한 적 있는 단어에 도착했을 때, 최소 단계를 갱신하거나 더 이상의 탐색을 중단하는 것이 가능하다.
• DFS탐색에는 스택을 사용한 반복형 구현을 사용한다. 이 때 스택에는 다음 단어와 단계를 넣는다.
• 탐색 중 타겟 단어를 만나면 탐색을 중단하고 현재까지의 최소값과 비교하여, 더 작은 값이 나오면 최소 단계값을 갱신한다.

 

  위의 사항들을 고려한 정답 코드가 아래와 같다.

// 주어진 단어가 변환이 가능한 단어인지 확인하여, 가능하면 true를 반환한다
function isChangeable(a, b) {
  let difference = 0;

  for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) difference++;
    if (difference > 1) return false;
  }

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

function solution(begin, target, words) {
  let answer = 0;

  // 단어 배열에 target이 존재하지 않을 시 0을 반환한다
  if (!words.includes(target)) return 0;

  // 방문 여부 & 해당 단어까지의 최소 단계 정보를 갖는 배열
  const visited = new Array(words.length).fill(-1);
  const stack = [[begin, 0]];

  // 반복형 DFS 구현
  while (stack.length) {
    const [current, length] = stack.pop();
    const newLength = length + 1;

    // 전에 방문한 이력이 있으면서 최소값을 갱신할 수 없는 경우
    if (visited[current] !== -1 && visited[current] < newLength) {
      continue;
    }

    visited[current] = newLength;

    // 타겟 단어에 도달했을 경우, 최소 단계를 비교한다
    if (current === target) {
      if (answer === 0) answer = length;
      else answer = Math.min(answer, length);
      continue;
    }

    words.forEach((el) => {
      if (isChangeable(current, el)) {
        stack.push([el, newLength]);
      }
    });
  }

  return answer;
}

---

• 그 전까지는 잘 몰랐는데, 질문 게시판에 테스트 케이스의 수에 대한 이야기가 많이 나오는 것을 보면 생각보다 프로그래머스 문제의 테스트 케이스 수는 다양하지 않은 것 같다...?
• 그에 따라 사실 저 코드가 완벽한 정답 코드가 될 수 있는지 좀 불안하긴 한데... 비교적 어렵지 않게 구현 방법을 짜내고 구현해낸 것에 일단 만족.
• 테스트 케이스의 찝찝함(?)과는 별개로, 늘 느끼지만 프로그래머스의 코드 에디터가 갖춰진 환경은 편하다. 백준 때는 node.js를 활용할 때 이래저래 애로사항이 있었기 때문에...