피로도

프로그래머스 level2. 완전 탐색 / DFS 피로도

문제링크

문제 설명

XX게임에는 피로도 시스템이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 각 던전마다 탐험을 시작하기 위해 필요한 “최소 필요 피로도”와 던전 탐험을 마쳤을 때 소모되는 “소모 피로도”가 있습니다.

유저의 현재 피로도 k와 각 던전별 “최소 필요 피로도”, “소모 피로도”가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

입출력 예

k = 80
dungeons = [[80,20],[50,40],[30,10]]
result = 3

풀이

유저가 탐험할 수있는 최대 던전의 수를 구해주어야 합니다. 탐험하면서 k 에서 dungeons[i][1] 를 빼가면서 dungeons[i][0] 보다 k 값이 큰 경우를 찾고 모든 조합 중 최대 값을 찾아줍니다.

방문해야 할 던전의 길이만큼 visited 를 만들어줍니다 [0,0,0]. 만약, 최소 필요 피로도보다 값이 크고, 방문한 적이 없는 노드인 경우에는 해당 노드를 방문한 것으로 표시해줍니다. (visited[i]=1)

그리고 하위 노드가 있다면 dfs 가 재호출 되는데, 이때 k-d[i][1] 된 k 값을 인자로 넣어주고 count 도 +1 해줍니다. dfs 가 시작하는 하위의 노드는 다시 0으로 만들어줍니다.

function solution(k, d) {
  const dLength = d.length;
  const visited = new Array(dLength).fill(0);
  let answer = 0;

  function dfs(k, cnt) {
    answer = Math.max(cnt, answer);

    for (let i = 0; i < dLength; i++) {
      if (k >= d[i][0] && !visited[i]) {
        visited[i] = 1;
        dfs(k - d[i][1], cnt + 1);
        visited[i] = 0;
      }
    }

    return answer;
  }

  dfs(k, 0);

  return answer;
}

알게 된 점

dfs 에 대해서 학습 & 방문 노드 처리 방법을 배웠다.