[프로그래머스] 피로도 - Java

이지연·2026년 1월 1일

DFS 백트래킹 완전탐색

코딩테스트 풀이(구현, 자료구조, 알고리즘)

목록 보기

34/50

프로그래머스 문제 URL

문제 요약

현재 피로도 k와 여러 개의 던전들이 주어진다.
각 던전은 입장에 필요한 최소 피로도와 소모 피로도로 구성되어 있다.

가능한 한 많은 던전을 탐험했을 때의 최대 탐험 가능 던전 수를 구하는 문제다.

핵심 아이디어

먼저 떠올릴 수 있는 방법은 단순히 “들어갈 수 있으면 들어가자”지만,
던전을 도는 순서에 따라 전체 가능한 탐험 수가 달라진다.
→ 예를 들어, 더 피로도가 큰 던전을 먼저 돌면 이후에 작은 던전을 못 돌 수도 있다.

따라서 가능한 모든 순서(순열) 를 탐색해야 한다.
던전 수가 최대 8개이므로, 총 경우의 수는 8! = 40320으로 완전 탐색이 가능하다.

이때 백트래킹(Backtracking) 으로 모든 경우의 탐색을 수행하면서,
“현재 피로도로 입장 가능한 던전만 탐험”하고,
가장 많이 돌 수 있는 횟수를 갱신한다.

DFS / 백트래킹 접근

visited[i]: i번째 던전을 이미 탐험했는가 여부
count: 현재까지 탐험한 던전 수
k: 현재 남은 피로도

모든 던전에 대해 다음 과정을 반복한다:

이미 방문했으면 패스.
현재 피로도(k)가 최소 필요 피로도 이상이면 탐험 가능.
방문 표시 → 피로도 차감 → 다음 깊이 탐색(재귀).
재귀 후 방문 기록 복구(backtracking).

전체 코드 (제출용)

class Solution {

    static int answer = 0;
    static boolean[] visited;

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

    static void backtrack(int k, int[][] dungeons, int count) {
        answer = Math.max(answer, count);

        for (int i = 0; i < dungeons.length; i++) {
            if (visited[i]) continue;

            if (k >= dungeons[i][0]) {
                visited[i] = true;
                backtrack(k - dungeons[i][1], dungeons, count + 1);
                visited[i] = false;
            }
        }
    }
}