[javascript] 프로그래머스, 피로도 (완전탐색, DFS)

완전탐색 챕터로 빼논 애들 거의다 DFS로 풀면 되어서

연습 엄청 된다 -ㅇ-

그 중에 제일 기본인것 같은 DFS 문제

 

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

프로그래머스

function solution(k, dungeons) {
    var answer = -1;

    // 던전 갯수만큼 방문 체크 배열
    var visited = new Array(dungeons.length).fill(0)
    
    // DFS(남은 hp와, 단계)
    function dfs (hp,lv) {
        //모든 던전을 시작점으로 돌아보자
        for(let i = 0; i<dungeons.length; i++){
           // 방문하지 않은, 현재의 피로도가 최소 피로도보다 크거나 같으면 진행
            if(visited[i]===0 && dungeons[i][0] <= hp) {
                // 방문체크
                visited[i] = 1;
                // 방문 던전만큼 피로도 감소, 다음레벨
                dfs(hp-dungeons[i][1], lv+1)
                // 돌고 와서 방문체크 돌려놓음 (다음 for문을 위해)
                visited[i] = 0;
            }
        }
        // 현재 레벨이 answer 보다 크면 업데이트해준다
        answer = Math.max(answer,lv)
    }
    
    // 주어진 피로도 k, 0단계로 시작
    dfs(k,0)
    return answer;
}

 

 

https://leejams.github.io/%ED%94%BC%EB%A1%9C%EB%8F%84/ 

코드 및 그림 여기 참조 ~