[JS] 피로도

 

프로그래머스

 

문제 이해

모든 경우를 탐색해야 한다. 탐험할 수 있는 최대 길이를 구하는 문제이므로 DFS를 사용해야 할 것 같다. 아직도 DFS를 구현하는 것이 힘들어서 다른 사람 코드를 참고했다.ㅜ

 

방법

깊이 우선 탐색은 방문한 것은 스택으로, 방문해야할 것을 큐로 저장해야한다.

왜냐하면 노드를 타고 최대한 깊게 들어간 후, 다시 경로를 타고 올라와서(스택) 다음 경로로 가야하기(큐) 때문이다.

 

function solution(k, dungeons) {
  let answer = 0;
  // 방문했는지 확인하기 위한 배열
  const visited = Array.from({ length: dungeons.length }, () => false);
  console.log(visited)

  // 완전탐색을 위한 DFS(남은 피로도, 진행단계)
  function DFS(hp, L) {

    // 던전의 수 만큼 반복한다.
    for (let i = 0; i < dungeons.length; i++) {

      // 방문하지 않았고 현재 남은 피로도가 최소 필요도 보다 크거나 같으면 실행
      if (!visited[i] && dungeons[i][0] <= hp) {
        console.log('hp :', hp, 'lv :',L ,'던전 idx :', i, dungeons[i])

        // 현재 들어온 던전을 방문 처리
        visited[i] = true;

        // DFS(현재 피로도 - 방문 던전, 진행단계 + 1)
        DFS(hp - dungeons[i][1], L + 1);

        // DFS 종료 후 방문을 끝내준다.
        visited[i] = false;
      }
    }

    // 가장 깊이 들어간 진행단계를 answer에 넣어준다.
    answer = Math.max(answer, L);
    
    // 만약 던전의 길이와 같으면 종료한다. (모든 던전을 탐험하는 경우가 가장 긴 경우이므로)
    if (answer === dungeons.length) {
      return answer;
    }
  }

  DFS(k, 0);

  return answer;
}

 

처음에는 위 코드를 보고, 어떻게 모든 경우를 탐색하는 건지 궁금했는데, `visited`가 방문한 노드로 이루어진 스택과 같은 역할을 하므로 모든 경우의 수를 탐색할 수 있는 것이었다.

 

 

참고

• 위 코드 출처