[오늘의 문제] 피로도

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

문제 설명
XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항
k는 1 이상 5,000 이하인 자연수입니다.
dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
dungeons의 가로(열) 길이는 2 입니다.
dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
"최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
"최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.
입출력 예
k dungeons result
80 [[80,20],[50,40],[30,10]] 3
입출력 예 설명
현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.
만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.
따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

※ 공지 - 2022년 2월 25일 테스트케이스가 추가되었습니다.

내가 작성한 코드문

class Solution {
    public int solution(int k, int[][] dungeons) {
        int answer = 0;
        
        // 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"
        // 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"
        // 유저의 현재 피로도 k와 
        // 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수
        // dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하
        // dungeons의 가로(열) 길이는 2
        // dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
        // "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
        // "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하
        
        for(int i = 0; i < dungeons.length; i++){
            int x1 = dungeons[i][0];// 이것도 전에 문제랑 똑같을지?
            int y1 = dungeons[i][1];
            
            int temp = dungeons[i][0]; // 시작점 보관
            int temp2 = dungeons[i][1];
            if(k >= x1){ // 현재 피로도가 최소 필요 피로도 보다 크거나 같다면?
                k = k - y1;// 현재 필요 피로도에서 소모 피로도를 뺀다.
                answer++;
            } else if(i + 1 < dungeons.length && k < x1) {// 만약 현재 피로도가 최소 필요 피로도보다 작을시 순서변경? 
                temp = dungeons[i][0];
                dungeons[i][0] = dungeons[i + 1][0];
                dungeons[i + 1][0] = temp;
                
                temp2 = dungeons[i][1];
                dungeons[i][1] = dungeons[i + 1][1];
                dungeons[i + 1][1] = temp2;
            }
        }    
        // 그렇다면 여기서 어떻게 건너 뛰고 그런걸 할수 있을지?? 
        // 탐험할 수 있는 최대 던전 수 반환
        return answer;
    }
}

채점 결과
정확성: 42.1
합계: 42.1 / 100.0
이 떴다.

🚨 현재 코드의 문제점 요약
단일 for문만 사용하고 있어, 던전 탐험 순서를 바꿔가며 시도하지 못함.

탐험 실패 시 단순히 다음 던전과 swap만 하고 끝.
하지만 이건 일부 케이스에서만 맞고, 모든 순서를 다 시도해봐야 정답이 나옴.

즉, 순열 전부 시도가 빠졌기 때문에 대부분의 테스트 케이스에서 오답이 나옴 → 점수 낮음.

✅ 정답 로직 (DFS + 백트래킹)
아이디어:
모든 던전 순서를 탐색 (순열)

각 순서대로 탐험하며 최대 몇 개 가능한지 확인

그중 가장 큰 값을 저장

요구사항이 만족하는 코드문

class Solution {
    boolean[] visited;
    int max = 0;

    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length]; // visited 배열: 어떤 던전을 방문했는지 기억
        dfs(0, k, dungeons); // DFS 시작 (depth = 0, fatigue = k)
        return max;
    }

    public void dfs(int depth, int fatigue, int[][] dungeons) {
        max = Math.max(max, depth);

        for (int i = 0; i < dungeons.length; i++) {
            int min = dungeons[i][0]; // 최소 필요 피로도
            int cost = dungeons[i][1]; // 소모 피로도

            // 아직 방문하지 않았고, 피로도가 최소 필요 피로도 이상이면 탐험 가능
            if (!visited[i] && fatigue >= min) { // 갈 수 있는 던전이면
                visited[i] = true; // 방문 표시
                dfs(depth + 1, fatigue - cost, dungeons); // 다음 탐색
                visited[i] = false; // 백트래킹: 다른 경우도 시도할 수 있게 원상복구
            }
        }
    }
}

우선 dfs, 백트래킹에 대한 개념 부족이 큰거 같다.

🧠 여기서 핵심:
dfs()는 가능한 모든 던전 순서를 시도해봄.

visited[i] = false를 통해 되돌아가서 다른 선택을 해볼 수 있게 만듦 — 이게 백트래킹이다.

🔁 백트래킹이 뭐야?
"모든 경우를 시도하되, 중간에 조건 안 맞으면 돌아가서 다른 경우를 시도하는 방식"

즉,

어떤 던전을 선택해서 진행해보고,

끝나면 선택을 되돌리고

또 다른 던전을 선택해서 진행하는 방식이다.

다른분들 풀이

class Solution {
    public static boolean check[];
    public static int ans = 0;

    public int solution(int k, int[][] dungeons) {
        check = new boolean[dungeons.length];

        dfs(k, dungeons, 0);

        return ans;
    }
    public static void dfs(int tired, int[][] dungeons, int cnt){
        for(int i=0; i<dungeons.length; i++){
            if(!check[i] && dungeons[i][0]<=tired){
                check[i] = true; // 방문 처리
                dfs(tired-dungeons[i][1], dungeons, cnt+1);
                check[i] = false; // 백트래킹
            }
        }
        ans = Math.max(ans, cnt);
    }
}

class Solution {
    int dfs(int k, int[][] dungeons) {
        int cnt = 0;
        for(int[] d : dungeons) {
            int a = d[0], b = d[1];
            if(a <= k) {
                d[0] = 9999;
                cnt = Math.max(1 + dfs(k - b, dungeons), cnt);
                d[0] = a;
            }
        }
        return cnt;
    }
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        return dfs(k, dungeons);
    }
}