🕊 Link

Lv3. 단어 변환 Javascript
https://programmers.co.kr/learn/courses/30/lessons/43163

🧑🏻‍💻 Code(javascript)

function solution(b, t, words) {
  if (!(words.includes(t))) return 0

  const v = new Array(words.length).fill(false) // visited
  const l = b.length
  const q = []
  let answer = 0

  const begin = { word: b, depth: 1 }
  q.push(begin)

  while (q.length) {
    const { word, depth } = q.shift()
    words.forEach((compare, index) => {
      let diffCount = 0
      for (let j = 0; j < l; j++) {
        if (word[j] !== compare[j]) diffCount++
      }
      if (diffCount == 1 && !v[index]) {
        if (compare == t) answer = depth
        q.push({ word: compare, depth: depth + 1 })
        v[index] = true
      }
    })
  }
  return answer
}

💡 Solution

BSF => 복습 풀이 참고

function solution(b, t, words) {
  if (!(words.includes(t))) return 0 // words가 target을 포함하고 있지 않을 경우, 0을 return

  const v = new Array(words.length).fill(false) // visited
  const l = b.length // 문자열 길이 확인
  const q = [] // queue
  let answer = 0

  const begin = { word: b, depth: 1 }
  q.push(begin) // initialize

  while (q.length) { // queue에 값이 있으면 loop
    const { word, depth } = q.shift() // q에서 shift한 값을 word, depth에 할당
    words.forEach((compare, index) => { // words를 돌면서 compare에 할당, index 확인
      let diffCount = 0
      for (let j = 0; j < l; j++) {
        if (word[j] !== compare[j]) diffCount++
        // word[j]와 compare[j]가 다르면 diffCount++
        // ex) "hit" vs "hot"의 각 자리 문자를 비교
      }
      // 한 번에 한 개의 알파벳만 바꿀 수 있으므로,
      // diffCount == 1 이면서 !v[index] 방문하지 않은 문자일 경우
      if (diffCount == 1 && !v[index]) {
        // compare의 값이 target과 같은 값을 depth에 할당 
        if (compare == t) answer = depth
        // queue push => 비교할 문자는 compare, depth는 현재 depth+1
        q.push({ word: compare, depth: depth + 1 })
        v[index] = true // 방문 체크
      }
    })
  }
  return answer
}

DSF 🚫

풀이는 통과하였으나, 더 먼 거리를 돌아가는 경로에 먼저 갔을 경우
이미 체크된 visited를 갈 수 없으므로, 오답의 가능성이 있을 것으로 예상됨
이 문제는 BSF 풀이가 더 적합할 것으로 판단

function solution(b, t, words) {
  if (!(words.includes(t))) return 0 // words가 target을 포함하고 있지 않을 경우, 0을 return

  const v = new Array(words.length).fill(false) // visited
  const l = b.length // 문자열 길이 확인
  const q = [] // queue
  let answer = 0

  const begin = { word: b, depth: 1 }
  q.push(begin) // initialize

  for (let i = 0; i < l; i++) {
    while (q.length) { // queue에 값이 있으면 loop
      const { word, depth } = q.pop() // q에서 pop한 값을 word, depth에 할당
      words.forEach((compare, index) => { // words를 돌면서 compare에 할당, index 확인
        let diffCount = 0 
        for (let j = 0; j < l; j++) {
          if (word[j] !== compare[j]) diffCount++ 
          // word[j]와 compare[j]가 다르면 diffCount++
          // ex) "hit" vs "hot"의 각 자리 문자를 비교
        }
        // 한 번에 한 개의 알파벳만 바꿀 수 있으므로,
        // diffCount == 1 이면서 !v[index] 방문하지 않은 문자일 경우
        if (diffCount == 1 && !v[index]) {
          // compare의 값이 target과 같으면서
          // answer에 현재 기록된 최소값보다 작은 경우 depth를 갱신
          if (compare == t && answer < depth) answer = depth
          // queue push => 비교할 문자는 compare, depth는 현재 depth+1
          q.push({ word: compare, depth: depth + 1 })
          v[index] = true // 방문 체크
        }
      })
    }
  }
  return answer
}

🔁 복습 풀이(BSF) ✔️

function solution(begin, target, words) {
  if (!words.includes(target)) return 0
  const visited = new Array(words.length).fill(0)
  const queue = []
  queue.push({ word: begin, depth: 0 })

  while (queue.length) {
    const { word, depth } = queue.shift()
    if (word === target) return depth
    words.forEach((newWord, index) => {
      if (!visited[index] && verify(word, newWord)) {
        queue.push({ word: newWord, depth: depth + 1 })
        visited[index] = 1
      }
    })
  }
}

function verify(word, newWord) {
  const length = word.length
  let diffCount = 0
  for (let i = 0; i < length; i++) {
    if (word[i] !== newWord[i]) diffCount++
  }
  return diffCount === 1 ? true : false
}

👨‍👦‍👦 Others

프로그래머스 - EHwooKim , 이현제

const diffOne = function(wordFirst, wordSecond) {
    let count = 0
    for (let i = 0; i < wordFirst.length; i++) {
        if (wordFirst[i] !== wordSecond[i]) {
            count += 1
            if (count >= 2) return false
        }

    }
    return true
}

const solution = function(begin, target, words) {
    if (!words.includes(target)) return 0
    let arr = [[begin, 0]]
    while (arr) {
        let [a, c] = arr.shift()
        for (const word of words) {
            if (diffOne(a, word)) {
                if (a === target) return c
                else arr.push([word, c + 1])
            }
        }
    }
}

👨🏻‍💻💭 Self Feedback

• BFS/DFS문제라고 해서 바로 머리를 굴렸지만, 과연 코테에서 문제를 받아들었을 때도 BFS/DFS 문제인지 알아챌 수 있을지
• 그림, 표, 그래프를 빠르게 그려보고 BFS/DFS인지 알아보자.
• 조금은 돌아서 가는 느낌. 다른 사람 풀이도 유심히 확인해보기.
  => BFS로 풀면 최소값을 찾을 필요가 없음.
  => 즉, BFS는 최단거리 최소경로 등을 찾기 적합함

• 2021.08.11 - 최초 작성

댓글 환영 질문 환영
by.protect-me