[프로그래머스/JAVA] 피로도 - 완전탐색

문제

 

 

 

풀이

던전 정보를 visited로 체크하면서 1부터 dungeons.length개까지의 순열을 만들어 유저가 최대로 방문 가능한 순열을 찾고, 그 개수를 세어준다.

visited[0] = true ----------> [80,20] 탐색완료

visited[1] = true ----------> [50,40] 탐색완료

visited[2] = true ----------> [30,10] 탐색완료

 

코드에서는 DFS의 깊이인 L 정보가 탐색한 던전의 개수가 된다.

현재 탐색한 던전의 개수인 L이 지금까지 탐색한 던전의 최대 개수인 answer보다 크면, 최댓값을 L로 업데이트하는 과정 반복

import java.util.*;
class Solution {
    static int answer = 0; 
    public int solution(int k, int[][] dungeons) {
        boolean[] visited = new boolean[dungeons.length];
        DFS(0, k, visited, dungeons);
        return answer;
    }
    
    static void DFS(int L, int k, boolean[] visited, int[][] dungeons){
        if(L>answer) {
            answer=L;
        }
        for(int i=0; i<dungeons.length; i++){
            if(!visited[i] && k>=dungeons[i][0]) {
                visited[i]=true;
                DFS(L+1, k-dungeons[i][1], visited, dungeons);
                visited[i]=false;
            }
        }
        // answer = Math.max(answer, L);
    }
}

 

answer에 값을 넣어주는 조건이 헷갈려서 21번째 줄 코드처럼 작성했는데, 11-13라인처럼 적어주는 것이 더 좋은 것 같다.