[프로그래머스] 피로도 / 자바(Java)

문제

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

프로그래머스

 

---

해설

각 던전을 확인하는데 소모 피로도와 현재 피로도의 차이, 최소 필요 피로도 2가지를 비교해야하기 때문에 완전탐색으로 모두 확인해보아야 합니다.

따라서 완전 탐색 중 dfs를 이용해서 해결했습니다.

방문여부를 확인할 배열 visited[], 가장 많이 돈 던전 수를 확인할 answer를 외부에 저장해 줍니다.

이후 dfs를 구성해 줍니다.

 

    public void dfs(int count, int k, int[][] dungeons){
        answer = Math.max(count,answer);
        for(int i=0;i<dungeons.length;i++){
            if(visited[i] || dungeons[i][0] > k) continue;
            
            visited[i] = true;
            dfs(count + 1, k - dungeons[i][1], dungeons);
            visited[i] = false;
        }
    }

 

count는 던전을 돈 횟수이기 때문에 각 시작마다 answer와 비교해줍니다.

이미 방문한 던전이거나 최소필요피로도를 비교해 dfs를 더 들어가지 못하도록 합니다.

---

코드

class Solution {
    int answer = 0;
    boolean[] visited;
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        dfs(0,k,dungeons);
        return answer;
    }
    
    public void dfs(int count, int k, int[][] dungeons){
        answer = Math.max(count,answer);
        for(int i=0;i<dungeons.length;i++){
            if(visited[i] || dungeons[i][0] > k) continue;
            
            visited[i] = true;
            dfs(count + 1, k - dungeons[i][1], dungeons);
            visited[i] = false;
        }
    }
}