[JavaScript] Programmers 단어 변환 (JS)

단어 변환

📚 문제 설명

words 배열과 begin과 target 단어가 있다고 한다.
begin 단어를 words 배열 안의 단어들로 아래와 같은 조건으로 단계적으로 바꾼 후, 최종적으로 target 단어로 바꾸고 싶다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어
begin이 "hit", target가 "cog",
words가 ["hot","dot","dog","lot","log","cog"]라면
"hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있다.

👨🏻‍💻 풀이 과정

이 문제는 최단거리를 구하는 것처럼 BFS를 사용해 풀 수도 있지만, 최근에 DFS를 많이 안썼기 때문에 DFS로 풀기로 생각했다.

따라서 전체적인 로직은 다음과 같이 구성했다.

• DFS() 함수의 인자로 현재 단어를 저장할 word, 지금까지 변환한 횟수 cnt, 이미 확인한 단어를 체크할 visited 배열을 받도록 했다.
• Check(word, goal) 함수를 이용해 word와 비교할 대상인 goal 단어를 비교하여 둘이 한개의 알파뱃만 다른지 확인.
• DFS() 함수에서 words 배열을 순회하며 다음 단어와 word를 Check()로 비교.
  • 만약 아직 가지 않은 단어이고 1개의 알파뱃만 다르면 재귀.

DFS 함수, Check 함수

      	// 두 단어의 알파뱃이 몇개가 다른지 확인.
        const Check = (word, goal) => {
            let cnt = 0;
            for (let i = 0; i < word.length; i++) {
                if (word[i] !== goal[i]) cnt++;
            }
            return cnt === 1;
        };
		// 깊이 우선 탐색
        const DFS = (word, cnt, visited) => {
          	// 만약 현재 단어가 target이면 종료.
            if (word === target) {
              	// 현재 answer와 cnt를 비교하여 최솟값으로 저장.
                answer = Math.min(answer, cnt);
                return;
            }
          	// words 배열 순회.
            for (let i = 0; i < words.length; i++) {
              	// 만약 아직 바꾸지 않은 단어이고 알파벳 하나만 바꾸면 된다면.
                if (!visited[i] && Check(word, words[i])) {
                    visited[i] = true;
                    DFS(words[i], cnt + 1,visited);
                    visited[i] = false;
                }
            }
        };

그 후 이제 몇가지 조건만 추가하여 전체 코드를 작성하면 된다.

1. 만약 words 배열에 target 단어가 없다면, 0리턴.
2. 만약 target 단어가 될 수 없다면 0리턴.
   • words의 최대 길이는 50이기 때문에 52의 값으로 answer를 초기화
   • 만약 answer 값이 바뀌지 않았다면, 0리턴.

전체 코드

    function solution(begin, target, words) {
        let answer = 52;
      	// 두 단어의 알파뱃이 몇개가 다른지 확인.
        const Check = (word, goal) => {
            let cnt = 0;
            for (let i = 0; i < word.length; i++) {
                if (word[i] !== goal[i]) cnt++;
            }
            return cnt === 1;
        };
		// 깊이 우선 탐색
        const DFS = (word, cnt, visited) => {
          	// 만약 현재 단어가 target이면 종료.
            if (word === target) {
              	// 현재 answer와 cnt를 비교하여 최솟값으로 저장.
                answer = Math.min(answer, cnt);
                return;
            }
          	// words 배열 순회.
            for (let i = 0; i < words.length; i++) {
              	// 만약 아직 바꾸지 않은 단어이고 알파벳 하나만 바꾸면 된다면.
                if (!visited[i] && Check(word, words[i])) {
                    visited[i] = true;
                    DFS(words[i], cnt + 1,visited);
                    visited[i] = false;
                }
            }
        };
      	// words 배열에 없을 경우.
        if (!words.includes(target)) return 0;
        DFS(begin, 0,new Array(words.length).fill(false));
      	// target으로 바꿀 수 없는 경우.
        return answer === 52 ? 0 : answer;
    }

🧐 후기

재귀에 visited 배열을 함께 인자로 보내지 않아서 오류가 발생해서 오랫동안 헤맸던 문제이다.