프로그래머스 단어 변환 JavaScript

김건호·2021년 10월 14일
0
post-custom-banner

문제링크

function solution(begin, target, words) {
    var answer = 0;
    
    if(!words.includes(target)) //예제 #2
// target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다. 예시 조건
        return 0;
    
    function oneChar(a,b) { // 한 글자만 차이가 나는지 확인하는 함수
        var diff=0;
        for(var i=0 ; i<a.length ; ++i) {
            if(a[i]!=b[i])
                ++diff;
        }
        if(diff==1)
            return true;
        else return false;
    }
    var visit=[]; // 방문했는지 기록하는 배열
    for(var i = 0 ; i<words.length ; ++i) 
        visit.push(false);
    var q=[];
    var temp=[];
    q.push(begin);
    
    while(q.length) {
        let w=q.shift(); // 방문하였으므로 큐에서 제거
        if(w==target)
            return answer;
        for(var i=0 ; i<words.length ; ++i) {
            if(oneChar(w,words[i]) && !visit[i]) { // 한글자 차이면서 방문을 안했다면 방문할 노드(temp)에 추가
                temp.push(words[i]); visit[i]=true;
            }
        }
        if(q.length==0) { // 큐가 비었다는 건, 현재 레벨의 모든 단어를 방문한것이므로
            ++answer; // 방문 수 증가
            q=temp; // 큐에 방문할 노드들 추가
            temp=[];
        }
    }
    
    return answer;
}

bfs로 단어들을 방문한다면 트리 구조가 나오게 됩니다.

         hit
         hot
      dot  lot
      dog  log
      cog

트리의 레벨이 단어를 바꾼 횟수이므로 바로 큐에 추가하지않고 임시배열에 추가해뒀다가, 레벨이 바뀔때 큐에 추가하였습니다.

profile
Ken, 🔽🔽 거노밥 유튜브(house icon) 🔽🔽
post-custom-banner

0개의 댓글