[프로그래머스] 깊이/너비 우선 탐색 - 단어 변환 문제 풀이 (feat.JS)

오늘은 프로그래머스에서 깊이/너비 우선 탐색(DFS/BFS) 관련 문제 중 단어 변환 문제 풀이를 JavaScript로 풀어보겠습니다. 오랜만에 JavaScript 언어로 문제를 풀게되어 기쁜 마음에 즐겁게 문제 풀이에 임하도록 하겠습니다.

 

 

프로그래머스 > 깊이/너비 우선 탐색(DFS/BFS) > 단어 변환 문제 풀이

 

 

 

 

Ω 문제 정보

• 문제명: 단어 변환
• 문제 난이도: Level 3
• 문제 푼 사람 수: 16550명
• 사용 가능 언어: 11개 (JavaScript 사용)

 

 

 

 

Ω 문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

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

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.
두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

 

프로그래머스 단어 변환 문제 풀이를 위해 문제 설명 내용을 정리해보겠습니다.

 

• 시작 문자열(begin)에서 목표 문자열(target)를 알파벳 하나씩만 바꾸어 문자열 리스트(words) 내 있는 단어를 통해 만들 수 있는 과정의 수 구하기
• Inputs
  • begin: 시작 문자열
  • target: 시작 문자열로 만들고자 하는 목표 문자열
  • words: 시작 문자열에서 목표 문자열을 만들기 위해 거쳐야하는 단어 리스트
• Output: words를 활용하여 begin → target으로 변환하기 위한 과정의 단계 수

 

 

 

 

Ω 제한 사항

º 각 단어는 알파벳 소문자로만 이루어져 있습니다.
º 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
º words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
º begin과 target은 같지 않습니다.
º 변환할 수 없는 경우에는 0를 return 합니다.

 

 

• 각 단어는 알파벳 소문자다.
• 3 ≤ 각 단어의 길이 ≤ 10, 모든 단어의 길이는 같다.
• 3 ≤ words의 길이 ≤ 50, 중복 단어는 없다.
• begin ≠ target
• 변환할 수 없는 경우는 0을 반환

 

 

 

 

Ω 입출력 예

begin	target	words	return
"hit"	"cog"	["hot", "dot", "dog", "lot", "log", "cog"]	4
"hit"	"cog"	["hot", "dot", "dog", "lot", "log"]	0

 

 

 

 

Ω 입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

 

 

 

 

Ω 알고리즘 만들기

1. words에 target 단어가 존재할 경우, begin 단어로 탐색을 시작한다.
2. words의 단어 리스트를 순서대로 깊이 우선 탐색을 한다.
   2-1. words 단어 중 현재 단어에서 1개만 다른 경우 선택한다.
3. 현재 선택한 단어가 target 단어랑 같을 때, 최소 이동 횟수를 저장한다.
4. 저장한 최소 이동 횟수를 반환한다.

 

 

이번 단어 변환 문제 풀이에서 활용한 알고리즘은 깊이 우선 탐색(DFS)입니다. DFS를 통해 begin 단어가 target 단어로 갈 수 있는지 여부를 판단하고 가장 짧은 이동 횟수를 구하도록 알고리즘을 만들어보았습니다.

 

 

 

 

Ω 코드 구현

function solution(begin, target, words) {
    var answer = 51;

    1. words에 target 단어가 존재할 경우, begin 단어로 탐색을 시작한다.
    if(words.includes(target)) {
        searchWords(begin, [], 0);
    }

    function searchWords(curWord, visited, count) {
        // 3. 현재 선택한 단어가 target 단어랑 같을 때, 최소 이동 횟수를 저장한다.
        if(curWord === target) {
            answer = Math.min(answer, count);
            return;
        }

        // 2. words의 단어 리스트를 순서대로 깊이 우선 탐색을 한다.
        for(let i = 0; i < words.length; i++) {
            // 2-1. words 단어 중 현재 단어에서 1개만 다른 경우 선택한다.
            if(visited[i] !== true && checkNextWord(curWord, words[i])) {
                visited[i] = true;
                searchWords(words[i], visited, count+1);
                visited[i] = false;
            }
        }
    }

    function checkNextWord(cur, next) {
        let differentWords = 0;

        for(let i = 0; i < cur.length; i++) {
            if(cur[i] !== next[i]) {
                differentWords++;
            }
        }

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

    // 4. 저장한 최소 이동 횟수를 반환한다.
    return answer === 51 ? 0 : answer;
}

 

 

단어 변환 문제 풀이에서 활용된 알고리즘은 깊이 우선 탐색(DFS)으로 searchWords() 함수를 재귀적으로 구현하였습니다. JavaScript 단어 변환 문제 풀이 재미있게 구현해보았습니다.

 

 

 

 

Ω 채점 결과

 

 

이번 프로그래머스 단어 변환 문제 풀이 결과는 정확성 테스트 케이스 5개를 모두 통과하여 문제 풀이를 완료하였습니다. 그럼 다음 문제로 찾아오도록 하겠습니다.