🔎 단어 변환

❓ 문제링크

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

📄 제출 코드

function solution(begin, target, words) {
    let visited = Array(words.length).fill(false);
    if (words.indexOf(target) == -1) return 0;
    else {
        return dfs(words, target, 0, begin, visited);
    }
    
}

let ans = Infinity;
function dfs(words, target, depth, goal, visited ) {
    if (goal == target) return depth;
    else {
        for (var i = 0; i < words.length; i++) {
            if (!visited[i] && checkWords(goal, words[i])) {
                visited[i] = true;
                ans = Math.min(ans, dfs(words, target, depth + 1, words[i], visited));
                visited[i] = false;
            }
        }
        return ans;
    }
}

function checkWords(a, b) {
    if (a.length != b.length) {
        return false;
    }
    
    let differentCnt = 0;
    for (var i = 0; i < a.length; i++) {
        if (a.charAt(i) != b.charAt(i)) {
            differentCnt++;
        }
        if (differentCnt > 1) {
            return false;
        }
    }
    return true;
    
}
let begin = "hit";
let target = "cog";
let words = ["hot", "dot", "dog", "lot", "log","cog"];
console.log(solution(begin, target, words));

먼저, 변환할 수 없는 경우에는 0를 return 합니다. 라는 구문이 있어 target이 words에 없으면 0을 리턴하고, 아닌 경우 dfs를 돈다.
dfs는 단어목록, target, 깊이, 단어, 방문배열을 가지고 dfs를 돈다.
dfs에서는 방문하지 않았고, 가장 비슷한 경우(두 단어의 글자 차이가 1인 경우)에만 dfs를 돈다.
ans에는 goal이 target과 같아졌을 여러 경우 중 최소 depth를 저장하여 리턴한다.

🎲 다른 코드

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

    const stack =[begin];
    const result = [];
    const visited = {};
    let current;
    visited[begin] = true;
    while(stack.length) {
        current = stack.pop();
        if(current === target) {
            answer = 1;
            break;
        }
        result.push(current);


        words.forEach(val => {
           if(!visited[val] && check(current, val) === 1) {
               visited[val] = true;
               stack.push(val);
           } 
        });
    }

    return answer ? result.length : 0;
}

function check(v1, v2) {
    let count = 0;
    for(let i = 0; i < v1.length; i++) {
        if(v1[i] !== v2[i]) {
            count++;
        }
    }

    return count;
}

많은 사람들이 bfs를 이용하여 푼 거 같았다.
stack에서 pop하여 current를 가져와 result에 push한다.
그 후 words를 돌면서 방문하지않았고, 단어 체크해서 다른게 1이면 방문체크를 하고, stack에 넣는다.
여기서 하나 배운거는 visited를 객체로 두어 단어를 key로 하여 방문체크한 점이다.