[javascript] 프로그래머스 - 단어 변환

🤔문제 해결

• Lv3 | BFS

1. begin 에서 시작하여 BFS 탐색
2. BFS는 target과의 거리를 알 수 있으므로
3. target과의 최단거리를 구해서 답을 출력
4. 아래의 코드에서는 visited와 words_obj를 사용했지만
   잘 짜보면 words_obj 하나로 충분히 구현할 수 있다!

 

💻소스 코드

function solution(begin, target, words) {
    var answer = 0;
    // 타겟이 워드에 없는 경우
    if (!words.includes(target)) {
        return answer
    }
    
    let n = words.length
    // visited 와 queue
    let visited = Array(n).fill(0)
    let q = [begin]
    
    // 단어의 인덱스를 객체에 저장
    const words_obj = {}
    for (let i in words) {
        words_obj[words[i]] = i
    }

    while (q.length > 0) {
        let c = q.shift()
        
        // 타겟 워드에 도달하면 끝
        if (c == target) {
            return visited[words_obj[c]]
        }
        for (let i in words) {
            if (visited[i] == 0) {
                let word = words[i]
                let diff = 0
                for (let j in word) {
                    if (c[j] != word[j]) {
                        diff++
                    }
                    if (diff > 1) {
                        break
                    }
                }
                if (diff == 1) {
                    q.push(word)
                    if (c == begin) {
                        visited[i] = 1
                    } else {
                        visited[i] = visited[words_obj[c]] + 1
                    }

                }
            }

        }
    }

    console.log(visited)
    return answer;
}

 

📕문제 확인

출처: 프로그래머스

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

코딩테스트 연습 - 단어 변환