[ALGORITHM NINJA] 프로그래머스 DFS 3번 단어변환

9306 단어 algorithmalgorithm

내코드

function solution(begin, target, words) {
  var answer = 100000;
  
  // str1이 str2로 변할 수 있는지를 체크한다.
  function isValidate(str1, str2) {
    let result = 0;
    for (let check = 0; check < str1.length; check++) {
      if (str1[check] === str2[check]) {
        result++;
      }
    }
    return result === str1.length - 1;
  }
  
  // 시작 문자열을 맨 뒷 방에 집어넣는다. ( 메인 함수에서 포문 돌리는 것을 막기위함 )
  words.push(begin);
  let visited = [];

  function dfs(location, count) {
    if (target === words[location]) {
      // 도착 문자열이면 그 때의 카운트가 지금 까지의 카운트 값보다 작은지를 검사한다. 
      // 지금 카운터값이 지금까지의 값보다 작다면 대입한다
      if (answer > count) answer = count;
    }

    // 중복되었으므로 리턴한다.
    if (visited.includes(location)) return;

    
    // 중복되지 않았으므로 방문한다. QR체크인한다..
    visited.push(location);

    
    // 현재 방에서 갈 수 있는 방들을 조사한다. 갈 수 있으면 호출.
    for (let check = 0; check < words.length - 1; check++) {
      if (isValidate(words[location], words[check])) dfs(check, count + 1);
    }
  }
  
  // 시작 단어에서 출발한다.
  dfs(words.length - 1, 0);
  
  // 100000이면 변할 수 없는 것이므로 0을 리턴, 그게 아니면 answer값
  return answer === 100000 ? 0 : answer;
}

아이디어

  • solution("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]);

    1. dfs(hit, 0)
    1. "hit" 방은 방문한 적이 없으므로 "hit"에서 변환이 되는 단어들을 조사한다.
    1. dfs(hot, 0+1)
    1. "hot" 방은 방문한 적이 없으므로 "hot"에서 변환이 되는 단어들을 조사한다.
    1. dfs(dot,0+1+1) dfs(lot,0+1+1)
    1. "dot" 방은 방문한 적이 없으므로 "dot"에서 변환이 되는 단어들을 조사한다.
    1. dfs(lot,0+1+1+1) dfs(dog,0+1+1+1)
    1. "lot" 방은 방문한 적이 없으므로 "lot"에서 변환이 되는 단어들을 조사한다.
    1. dfs(dot,0+1+1+1+1) dfs(lot,0+1+1+1+1)
    1. dot lot 둘 다 방문한적이 있으므로 리턴한다.
    1. dfs(dog,0+1+1+1)
    1. "dog"는 방문한 적이없으므로 "dog"에서 변환이 되는 단어들을 조사한다.
    1. dfs(log,0+1+1+1+1) dfs(cog,0+1+1+1+1)
    1. "log"는 방문한 적이 없으므로 "log"에서 변환이 되는 단어들을 조사한다.
    1. dfs(dog,0+1+1+1+1+1) dfs(cog,0+1+1+1+1+1)
    1. dog는 중복되므로 리턴, cog는 타겟 단어이므로 이때의 카운트 값을 answer에 저장한다.
    1. dfs(cog,0+1+1+1+1)
    1. cog는 타겟 단어이므로 이때의 카운트 값이 이전 카운트 값보다 작은 지 점검한다. 5>4이므로 지금의 카운트 값을 answer에 저장한다.

좋은 웹페이지 즐겨찾기