[프로그래머스 - 자바(JAVA)] 32 : 피로도

목차

▸ 피로도

---

✅ 피로도 : Lv.2

▼ 문제

출처: 프로그래머스 코딩테스트 연습 > 완전탐색 > 피로도

▼ 내 풀이

• 우선, 가능한 경우의 수를 모두 탐색하여 방문한 던전의 수 중 가장 큰 수를 리턴하는 식으로 문제를 풀었다.
• 해당 던전에 방문 여부를 저장하는 boolean 타입의 배열을 생성했다.
• 또한, 던전을 방문하는 순서의 경우의 수 모두를 탐색하는 메서드를 만들었다.
• 이때, 반복문을 활용하여 다시 이 메서드를 호출함으로써 모든 경우의 수를 탐색할 수 있다.
• 예를 들어, dengeons 배열이 [[80,20],[50,40],[30,10]] 일때, dfs메서드를 통해서 80인 던전이 방문 처리되고 이 상태에서 다시 dfs를 호출한다.

class Solution {
    public int max;
    
    public int solution(int k, int[][] dungeons) {
        boolean[] visited = new boolean[dungeons.length];
        dfs(k, dungeons, visited);

        return max;

    }
    public void dfs(int k, int[][] dungeons, boolean[] visited) {
        int count = 0;
        for(int i = 0; i<visited.length; i++) {
            if(visited[i]) {
                count++;
            }
        }
        if(count > max) {
            max = count;
        }


        for(int i = 0; i<dungeons.length; i++) {
            if(!visited[i] && dungeons[i][0] <= k) {
                visited[i] = true;
                dfs(k-dungeons[i][1], dungeons, visited);
                visited[i] = false;
            }
        }
    }
}

---