[JavaScript][node.js] 프로그래머스 피로도

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87946

프로그래머스

풀이과정

S1 - 탐험 가능한 던전의 수를 세는 함수를 따로 만들기

count 함수

function count(arr, start) {
    let life = start;
    let count = 0;
    
    for(const item of arr) {
        const [req, minus] = item;
        if (req <= life && life - minus > 0) {
            count++;
            life -= minus;
        }
        else {
            return count;
        }
    }
    return count;
}

1. arr의 item, 즉 던전들을 순회
2. 입장에 필요한 req 보다 남은 피로도가 같거나 크고 && 남은 피로도(life)에서 minus만큼 소모해도 피로도가 0보다 크다면
3. 탐험이 가능하므로 count++, 남은 피로도(life)에서 minus만큼 빼주기
4. 탐험이 불가능하면 count return

dfs 함수

function dfs(pick, dungeons, visited, k) {
    if (pick.length === dungeons.length) {
        return count(pick, k);
    }
    
    let m = 0;
    dungeons.forEach((dungeon, i) => {
      if(!visited[i]) {
          pick.push(dungeon);
          visited[i] = 1;
          m = Math.max(m, dfs(pick, dungeons, visited, k));
          pick.pop();
          visited[i] = 0;
      }  
    });
    
    return m;
}

1. dfs()로 던전을 탐험할 수 있는 모든 순서 찾기
2. 순서 배열을 찾았으면 해당 배열을 count()로 넘겨 탐험할 수 있는 던전 개수 찾기
3. 탐험할 수 있는 던전 개수의 최댓값을 m에 업데이트

S2 - DFS 안에서 다 해결

function dfs(count, dungeons, visited, life) {
    let m = count;
    dungeons.forEach((dungeon, i) => {
      if(!visited[i] && dungeon[0] <= life) {
          visited[i] = 1;
          m = Math.max(m, dfs(count + 1, dungeons, visited, life - dungeon[1]));
          visited[i] = 0;
      }
    });
    
    return m;
}

1. dungeons 순회
2. 아직 방문하지 않은 던전이고, 입장이 가능하다면 (dungeon[0] <= life)
3. 방문처리, dfs 재귀
   1. 아직 방문하지 않은 곳을 계속해서 방문 시도
   2. 그러다 모든 던전을 순회하면, m을 return
   3. 이때 m은 지금까지의 count max값
4. 현재 m값과 3에서 return한 m 값 중 큰 값을 m에 다시 저장
5. 방문 해제, 새로운 던전 탐험

depth1에서 1을 return하는 경우는 생략하였다.

최종코드

function dfs(count, dungeons, visited, life) {
    let m = count;
    dungeons.forEach((dungeon, i) => {
      if(!visited[i] && dungeon[0] <= life) {
          visited[i] = 1;
          m = Math.max(m, dfs(count + 1, dungeons, visited, life - dungeon[1]));
          visited[i] = 0;
      }
    });
    
    return m;
}

function solution(k, dungeons) {
    const visited = new Array(dungeons.length).fill(0);
    const answer = dfs(0, dungeons, visited, k);
    return answer;
}

인사이트

• dfs를 순열 또는 조합을 만드는 데만 사용한다고 생각하지 말자. 가지로 뻗어나가는 형태는 dfs bfs 의심하기
• depth와 기타 매개변수를 잘 활용하자