[콭] DFS 정복

완전탐색에 적합.

피로도

문제

던전 방문 순서 변경을 통해 용사의 피로도를 조절하여 방문할 수 있는 던전의 최대값을 구하시오.

접근방법

DFS을 통한 완전탐색.
깊이 탐색을 통해 해당 결과 값이 유효한지 판단하고 아니라면 방문 표시를 삭제해 다음에 방문할 수 있도록 해준다.

javascript 코드

function solution(k, dungeons) {
    let answer = -1;
    
    const len=dungeons.length
    const visited=Array(len).fill(0)
    
    dfs(k,0)
    
    function dfs(k,cnt){
        if(cnt>answer) answer=cnt
        for(let i=0;i<len;i++){
            if(k>=dungeons[i][0]&&visited[i]===0){
                visited[i]=1
                dfs(k-dungeons[i][1],cnt+1)
                visited[i]=0
            }
        }
    }
    
    
    return answer;
}

function solution(k, dungeons) {
    let answer = -1;
    
    const len=dungeons.length
    const visited=Array(len).fill(false)
    
    function visit(hp,cnt){ 
        if(cnt>answer) answer=cnt
        for(let i=0;i<len;i++){
            const [min,con]=dungeons[i]
            if(hp>=min&&!visited[i]) {
                visited[i]=true
                visit(hp-con,cnt+1)
                visited[i]=false
            }
        } 
    } 
    visit(k,0)
    return answer;
}

단어 변환

문제

words의 문자열 배열을 이용해 begin의 문자를 하나씩 바꿔서 target으로 만들어라.

접근 방법

완전탐색. BFS 가능.

코드

function diff(words, target, visited, curCnt) {
  let obj = {};
  let len=words.length

  //target과의 차이 저장
  words.forEach((word) => {
    let dCnt = 0;
    for (let i = 0; i <= len; i++) {
      if (word[i] !== target[i]) dCnt++;
    }
    obj[word] = dCnt;
  });

  let arr = [];
  //target과 문자가 1개만 다른 문자열을 저장
  for (let i = 0; i < len; i++) {
    if (obj[words[i]] === 1 && !visited[i]) {
      arr.push([words[i], i, curCnt]);
    }
  } 
  return arr;
}
function solution(begin, target, words) {
  let num = 0;

  const len = words.length;

  let visited = new Array(len).fill(false);

  let visit = [];
  visit = diff(words, begin,  visited, num);

  while (visit.length) {
    let [curWord, idx, cnt] = visit.shift(); 

    //target 도달 시 카운트 반환
    if (curWord === target) return cnt + 1;
    
    if (visit[idx]) continue;//방문한 노드 통과
    visited[idx] = true;//방문처리

    //하나만 다른 문자열들을 배열에 저장
    let arr = diff(words, curWord, visited, cnt + 1);
    visit = [...visit, ...arr];
  }
  return 0;
}

출처 : 이코테, 프로그래머스