[코딩테스트 javascript] 단어변환 - BFS , 그래프 탐색 알고리즘, 너비탐색알고리즘

단어변환

 

프로그래머스

 

문제 설명

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

 

 

해결 방법

1. 최단거리는 BFS 즉, Queue를 이용한다.

- DFS는 overstack의 가능성이 커서 BFS로 푸는 것이 좋다.

- 참고 : https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EB%8B%A8%EC%96%B4%EB%B3%80%ED%99%98-JS

 

2. 하나의 객체를 생성하여 {str:count}로 구성한다.

- 최종 return은 객체[target]

- 객체에 변수를 키로 넣기 위해 중괄호([])에 담아야 한다.

let obj = { [begin] : 0 }

3. 연결되어 있는지 확인하는 함수를 생성한다.

- str과 words 원소와 다른 문자열이 1개인지 확인해야 한다.

function connected(str1,str2) {
	let count = 0 ;
    for (let i in str1) {
    	if (str1[i] !== str2[i]) count++}
    return count===1?true : false
 }

4. BFS 확인하는 코드 작성한다.

- 차례로 돌면서 obj에 새로운 str을 키값으로 하고 , 현재 str의 value +1을 value로 더해준다.

while(queue.length) {
	const cur = queue.shift();
    for(let s of words) {
    	if(isConnected(cur,s) && !visited[s]) {
        	queue.push(s);
            visited[s] = visited[cur]+1
            }
    }
 }

 

 

 

5. 최종 코드

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