[JS] 힌트 2Level / 완전탐색 / 피로도

문제 설명

문제 풀이 방법

• 나는 이 문제를 보고 dfs로 풀자는 생각을 못하고 순열을 이용해 풀려했다.....
• dfs로 풀어야지 완전탐색이 가능하다고 생각했지만 dfs 구현을 잘 못해서 결국 힌트를 봤다....
• dfs는 각 노드별 방문여부를 체크할 수 있는 배열을 만들고
  재귀를 이용해 문제를 풀어간다.
• 내가 낮설었던 것은 재귀한 뒤 방문여부 배열을 다시 초기화 하는 것이였다.

 

코드

const solution = (k, dungeons) => {
    // dfs로 문제를 풀면 방문하는 노드가 방문을 했었는지 기록하는 것이 중요하다. (무한 루프에 빠질 수 있음)
    let answer = 0;
    let visited = Array(dungeons.length).fill(false);
    
    const dfs = (point, temp) => {
        for(let i=0; i<dungeons.length; i++){
            if(!visited[i] && point >= dungeons[i][0]){
                visited[i] = true;
                dfs(point - dungeons[i][1], temp + 1);
                visited[i] = false;
            }
        }
        // 값 비교는 for문에서 모든 노드를 방문했거나 피로도가 필요 피로도 보다 적을 때 실행된다.
        answer = Math.max(answer, temp)
    }
    dfs(k, 0)
    return answer;
}