[프로그래머스 고득점 Kit] 피로도 자바 풀이 및 정답

문제요약)

- 던전 출입에 필요한 피로도, 클리어시 소모되는 피로도 주어짐

- 최대한 많은 던전 돌았을때의 클리어 던전수 리턴

 

주의점)

- X

 

풀이방법)

1. 모든 던전 케이스를 확인해야해서 DFS로 완전탐색

2. 이미 돈 던전은 전역으로 방문 배열 잡기

3. 방문배열, 피로도 등 확인해서 던전 돌 수 있는지 판단

4. 뎁스를 answer에 저장

 

DFS를 통해 완전탐색을 해야하는 유형이 문제인데 풀이가 바로 떠오르지 않아서 던전이 A, B, C 총 3개인 경우로 생각하고 재귀로 들어가는 과정을 그림을 그려보았습니다.

public class Fatigue {
    static boolean[] visited;
    static int answer = 0;
    static boolean flag;
    public static void main(String[] args) {

        // 모든 던전 탐험 가능한 경우
        int k2 = 300;
        int[][] dungeons2 = {{100, 20}, {150, 30}, {200, 40}};
        System.out.println(solution(k2, dungeons2));  // 3

        // 모든 던전 탐험 불가능한 경우
        int k3 = 80;
        int[][] dungeons3 = {{100, 30}, {120, 40}, {150, 50}};
        System.out.println(solution(k3, dungeons3));  // 0

        // 던전이 한 개인 경우
        int k4 = 150;
        int[][] dungeons4 = {{120, 30}};
        System.out.println(solution(k4, dungeons4));  // 1
    }

    public static int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        DFS(0, k, dungeons);
        return answer;
    }

    public static void DFS(int depth, int remain, int[][] dungeons) {
        // 이미 모든 던전을 다 돌 수 있는 케이스를 찾았다면 더 진행할 필요x
        if (flag) {
            return;
        }
        // 오면 일단 던전 다 돌기
        for (int i=0; i<dungeons.length; i++) {
            // 방문했거나 피로도가 부족하면 해당 던전 건너뛰기
            if (visited[i] || remain - dungeons[i][0] < 0) {
                continue;
            }

            // 방문 가능하면 방문하면서 다음 뎁스로 넘어가기
            visited[i] = true;
            int cost = dungeons[i][1];
            DFS(depth + 1, remain - cost, dungeons);
            visited[i] = false;
        }

        answer = Math.max(answer, depth);
        if (answer == dungeons.length) flag = true;
    }

}