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

접근 방식

• 한글자만 다른 단어들로 그래프를 만들어야 한다.
• 한글자만 다른지 알기 위해서 해당 함수를 만들어야 한다.
• 한글자만 같은 word를 통해 그래프 만들기
• 깊이 우선 탐색을 통해 최솟값 찾기

1. 한글자만 다른지 알기 위해서 함수

글자 수는 같으니까 인덱스로 접근해서 판단하기

const begin = "hit";
const words = ["hot", "dot", "dog", "lot", "log", "cog"];


const countMatchingCharacters = (prev, next) => {
  let count = 0;
  for(let i=0; i<prev.length; i++){
      if(prev[i]===next[i]){
      	count++;
      }
  }
  
  return count;
}

words.map((word)=>console.log(countMatchingCharacters("hit", word)));

2. 한글자만 같은 word를 통해 그래프 만들기

let graph = {};

...

words.map((prev)=>{
  graph[prev] = [];
  words.map((next)=>{
    if(countMatchingCharacters(prev, next) === 1){
        graph[prev].push(next); 
    }
  });
});

console.log(graph);

3. 깊이 우선 탐색을 통해 최솟값 찾기

const dfs = (word, graph, target) => {
  let stack = [word];
  let visit = new Set();
  let count = 0;
 
  while(stack.length>0){
    word = stack.pop();
    
    //방문을 했던 적이 있는지?
    if(!visit.has(word)){
      //target이랑 같으면 return
      if(word === target) return count;
      visit.add(word);
      count++;

      for(let neighbor of graph[word]){
		stack.push(neighbor);
        console.log(stack);
      }
    }
  }
  
  return count;
}

console.log(dfs('hot', graph, 'cog'));

4. begin과 하나만 다른 얘들만 dfs 돌리고 count를 return 받기

const beginArray = words.filter((word)=>countMatchingCharacters(begin, word)===1); 

let minArray = [];

beginArray.map((word)=>{
  minArray.push(dfs(word, graph, target)+1);
})

return Math.min(...minArray);

---

최종 풀이 링크

참고