피로도

문제

유저가 일정 피로도를 가지고 던전을 탐험하려고 합니다. 각 던전마다 탐험을 시작하기 위해 필요한 '최소 필요 피로도'와 탐험을 마쳤을 때 소모되는 '소모 피로도'가 주어집니다.

유저의 현재 피로도 k와 각 던전별 피로도 정보가 담긴 2차원 배열 dungeons가 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 반환하는 문제입니다.

• 던전의 개수는 1 이상 8 이하입니다.
• 최소 필요 피로도는 항상 소모 피로도보다 크거나 같습니다.

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

풀이 1: 순열 생성 후 일괄 검사

가능한 모든 던전의 방문 순서를 순열로 먼저 생성한 뒤, 완성된 순서 목록을 바탕으로 피로도 조건을 시뮬레이션하는 방법입니다.

1. 순열 생성: visited 배열과 List를 활용하여 던전 인덱스로 구성된 모든 순열을 구합니다.
2. 조건 검사: 리스트의 길이가 전체 던전 수와 같아지면(순서가 모두 정해지면), 해당 순서대로 던전을 순회합니다.
3. 피로도 시뮬레이션: 현재 던전의 최소 필요 피로도보다 크거나 같을 때만 피로도를 차감하고 카운트를 올립니다. 조건에 맞지 않으면 즉시 반복을 종료(break)합니다.
4. 최댓값 갱신: 시뮬레이션이 끝날 때마다 최대로 탐험한 던전 수(ans)를 갱신합니다.

던전의 개수가 최대 8개이므로 8! (40,320) 가지의 경우의 수만 확인하면 되어 충분히 통과 가능한 로직입니다.

코드 1: 순열 생성 후 일괄 검사

import java.util.*;

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

    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        go(dungeons, k, new ArrayList<>());

        return ans;
    }

    void go(int[][] dungeons, int k, List<Integer> list) {
        // 모든 던전의 방문 순서가 정해졌을 때
        if (list.size() == dungeons.length) {
            int cnt = 0;

            for (int i : list) {
                // 남은 피로도가 최소 필요 피로도보다 적으면 탐험 불가
                if (dungeons[i][0] > k) break;

                cnt++;
                k -= dungeons[i][1];
            }

            ans = Math.max(ans, cnt);
            return;
        }

        // 순열(Permutation) 생성
        for (int i = 0; i < dungeons.length; i++) {
            if (visited[i]) continue;

            visited[i] = true;
            list.add(i);

            go(dungeons, k, list);

            // 백트래킹 (원상 복구)
            visited[i] = false;
            list.remove(list.size() - 1);
        }
    }
}

풀이 2: 상태를 전달하는 최적화된 백트래킹

리스트에 방문 순서를 모두 모아두었다가 나중에 검사하는 대신, 재귀 탐색을 진행하면서 피로도 조건에 맞는 곳만 방문하도록 최적화한 방법입니다.

1. 상태 전달: DFS 재귀 함수의 매개변수로 현재 남은 피로도(k)와 현재까지 탐험한 던전 수(cnt)를 직접 전달합니다.
2. 가지치기 (Pruning): 반복문을 돌며 아직 방문하지 않은 던전 중, '현재 남은 피로도가 최소 필요 피로도 이상인 경우(k >= dungeons[i][0])'에만 재귀 탐색을 진행합니다. 갈 수 없는 던전은 애초에 탐색하지 않으므로 불필요한 연산이 크게 줄어듭니다.
3. 실시간 최댓값 갱신: 매 탐색마다 ans = Math.max(ans, cnt)를 수행하여 항상 최댓값을 유지합니다. 컬렉션(List)을 관리할 필요가 없어 코드가 훨씬 간결해집니다.

코드 2: 상태를 전달하는 최적화된 백트래킹

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

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

        // 초기 피로도 k와 탐험한 던전 수 0을 전달하여 탐색 시작
        dfs(k, dungeons, 0);

        return ans;
    }

    void dfs(int k, int[][] dungeons, int cnt) {
        // 매 탐색마다 최대 탐험 횟수 갱신
        ans = Math.max(ans, cnt);

        for (int i = 0; i < dungeons.length; i++) {
            // 아직 방문하지 않았고, 현재 피로도로 탐험 가능한 던전인 경우에만 탐색 (가지치기)
            if (!visited[i] && k >= dungeons[i][0]) {
                visited[i] = true;

                // 피로도를 차감하고, 탐험 횟수를 1 늘려서 다음 깊이로 이동
                dfs(k - dungeons[i][1], dungeons, cnt + 1);

                // 백트래킹 (원상 복구)
                visited[i] = false;
            }
        }
    }
}