[프로그래머스][Javascript]피로도

문제

피로도

프로그래머스

 

 

완전탐색을 필요로 하는 문제이다. 

그중 dfs를 이용해 풀 수 있다. 

 

코드

//경로탐색#네트워크#조합만들기🌰
//dfs🌰#bfs
//visited
//재귀함수

function solution(k, dungeons) {
    let d = dungeons;
    let visited = Array(d.length).fill(0) 
    let answer = 0;
    function dfs(k,result){
        answer = answer <result ? result: answer;
        
        for(let i in d){
            if(k>=d[i][0] && visited[i] ==0 ){
                visited[i] =1;
                dfs(k-d[i][1],result+1);
                visited[i] =0;
            }
        }
        
        return answer;
    }
    
    return dfs(k, 0);
}

 

✅checkpoint!

let arr = Array(length).fill(0)	length길이의 0으로 채워진 배열 선언하
max = max <new_value ? new_value : max	가장 큰 값 찾기

 

💡아이디어 요약

dfs를 이용한 완전탐색

조합을 구하고 서로 비교하는 문제이다. -> dfs visited배열을 이용해 중복 check되지 않도록 한다.  재귀함수를 이용해 dfs를 구현한다.

 

여러 객체들이 연결되어 있는 자료구조에서 특정 개체를 찾기 위한 알고리즘
대표적 문제 유형	1.경로탐색 유형(최단거리, 시간) 2.네트워크 유형(연결) 3.조합유형(모든 조합 만들기 후 비교)
dfs	재귀함수
bfs	Queue, LinkedList