프로그래머스 : 단어 변환 - javascript (bfs)

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=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 함수를 작성해주세요.

제한사항

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

입출력 예 설명

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

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

문제풀이 힌트 

문제를 보고 어떻게 풀어야 하는지 감 잡는게 제일 ~ 어려운 문제였던 것 같다. 

문자와 배열로 주어진 것들을 어떻게 노드로 생각하고 간선으로 연결할지 고민을 해야 한다. 

 

먼저 이 부분을 보고 규칙을 알아야 한다. 

주어진 문자끼리 철자 하나만 다를때 연결된 걸 알 수 있다. 

4

문제를 이해했는가? 

즉,  bigin('hit')으로 시작해서 target('cog')으로까지 도착하는데 몇번이 걸리냐? 

다만,  연결은 철자 하나씩만 다른 문자끼리 되어있다.

target으로 도착 못하면 0을 출력해라 ! 

 

자 문제 구성을 시작해보자. 

함수를 두개 만들어야 한다. 

1) 두 문자를 비교하는 함수 => 철자가 하나만 다르면 true 

2) bfs를 이용해서 target 문자까지 몇번만에 갈 수 있는지 구하는 함수 

 

정답 풀이 코드 

function solution(begin, target, words) {
    const visited = {
        [begin] : 0
    }
    const queue = [begin]; 
    while(queue.length){
        let cur = queue.shift(); 
        if(cur === target) break; 
       for(const word of words){
            if(isConnected(cur, word) && !visited[word]){
                visited[word] = visited[cur] + 1; 
                queue.push(word); 
            }
       }
    }
    return visited[target] ? visited[target] : 0
}
function isConnected(str1, str2){
    let cnt = 0; 
    for(let i=0; i<str1.length; i++){
        if(str1[i] !== str2[i]) cnt++; 
    }
    return cnt === 1 ? true: false ; 
}

의사 코드 추가

//bfs함수 
function solution(begin, target, words) {
    const visited = {
        [begin] : 0
    }
    const queue = [begin]; 
    while(queue.length){
        let cur = queue.shift(); //큐에서 맨 앞 문자 꺼내기 
        if(cur === target) break; //꺼낸 문자가 target가 같다면 반복문을 끝낸다. 
       for(const word of words){ //현재 문자랑 한개 철자만 다른거 탐색하기 
            if(isConnected(cur, word) && !visited[word]){ // 아직 visited에 입력이 안되어 있어야함
                visited[word] = visited[cur] + 1; //몇번째에 방문한건지 입력 
                queue.push(word); 
            }
       }
    }
    return visited[target] ? visited[target] : 0
}
//하나 철자 빼고 일치하는지 확인하는 함수 
function isConnected(str1, str2){
    let cnt = 0; 
    for(let i=0; i<str1.length; i++){
        if(str1[i] !== str2[i]) cnt++; 
    }
    return cnt === 1 ? true: false ; 
}