[프로그래머스 lev3/JS] 단어 변환

문제 출처

프로그래머스 lev3 - 단어 변환

나의 풀이

1차시도(80/100, 시간초과)

function solution(begin, target, words) {
  if(!words.includes(target)) return 0

  let answer = Number.MAX_SAFE_INTEGER
  
  const dfs = (L, str) => {
    if(L >= words.length) return
    if(str === target) {
      answer = Math.min(answer, L)
    }

    for(let i=0; i<words.length; i++){
      let cnt = 0
      for(let j=0; j<words[i].length; j++){
        if(words[i][j] !== str[j]) cnt++
      }
      if(cnt === 1) dfs(L+1, words[i])
    }
  }
  dfs(0, begin)
  return answer
}

console.log(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
console.log(solution("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))

2차시도 (통과)

check 배열을 생성해서 중복을 추적해줬다.

이미 한번 밟은 단계라면 ch[i]=1로 체크해준다.
단계가 짧아지려면 이미 밟은 단계를 또 밟는 중복이 발생해서는 안 된다.

function solution(begin, target, words) {
  if(!words.includes(target)) return 0

  let ch = Array.from({length: words.length}, () => 0)
  let answer = Number.MAX_SAFE_INTEGER

  const dfs = (L, str) => {
    if(L >= words.length) return
    if(str === target) {
      answer = Math.min(answer, L)
    }

    for(let i=0; i<words.length; i++){
      let cnt = 0
      for(let j=0; j<words[i].length; j++){
        if(words[i][j] !== str[j]) cnt++
      }
      if(cnt === 1 && ch[i] === 0) {
        ch[i] = 1
        dfs(L+1, words[i])
        ch[i] = 0
      }
    }
  }
  dfs(0, begin)
  return answer
}

다른 풀이 (bfs)

function solution(begin, target, words) {
  let visited = []
  let queue = []
  let min = 0

  if(!words.includes(target)) return 0 

  queue.push([begin, min])
  while(queue){
    let [v, step] = queue.shift()

    if(v === target) return step

    words.forEach(word => {
      let cnt = 0

      if(visited.includes(word)) return 

      for(let i=0; i<word.length; i++){
        if(cnt>1) break
        if(word[i] !== v[i]) cnt++
      }

      if(cnt === 1){
        queue.push([word, ++step])
        visited.push(word)
      }
    })
  }
  return min
}