[프로그래머스3단계] 단어 변환 with 자바스크립트(깊이 우선탐색 dfs)

문제설명

두 개의 단어 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 함수를 작성해주세요.

 

주의사항

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

입출력예시

코드

function solution(begin, target, words){
    let answer = 0;
    let ch = Array.from({length: words.length}, ()=>false);


    function dfs(cur, target, step){
        if(cur===target){
            if(answer === 0 || answer > step){
                answer= step
            }
            return;
        }

        for(let i=0; i< words.length; i++){
            if(ch[i]) continue;
            let diffCount = 0;

            for(let k=0; k<words[i].length; k++){
                if(words[i][k]!==cur[k]){
                    diffCount += 1
                }
            }

            if(diffCount===1){
                ch[i] =true;
                dfs(words[i],target,step+1);
                ch[i]=false;
            }
        }
    }
    dfs(begin, target, 0)
    return answer;
}

 

해석

방문 체크를 위한 배열을 하나 만들고, dfs함수를 호출한다.

 

dfs 함수 내부에서 cur === target이 같아질때 answer에 값을 넣기 위해 조건문을 작성한다.

두개의 조건은 1) answer=0인 경우(바뀌었다면 0이 나올수 없다.), 2)많은 경우의 수 중 최소 step일 경우에만 리턴해야하기 때문에 step의 가장 작은 값을 answer에 넣어준다.

 

words의 배열을 돌면서 스펠링이 하나틀린것을 찾고, 찾는다면,  그 단어에 방문했다는 체크와 그 단어를 가지고 dfs함수를 다시 호출한다. 

 

한줄평

많이 어려웠다. 처음에 아무생각도 안나서 레퍼런스 코드를 보고 분석하고 외워버렸다. 이렇게 흘러가는구나. 이해하고 자기 혼자 설명하면서 반복했다. 이와 비슷한 문제를 오늘 토이에서 봤는데 하아..아직 활용하는게 아쉽다. 토이는 저녁에 마저하는걸로..

이번에 제대로 배운건 continue와 break의 활용법

continue는 바로 다음단계로 넘어가고, break는 반복문을 나간다.

 

링크

https://programmers.co.kr/learn/courses/30/lessons/43163