[프로그래머스] 피로도 (DFS)

문제 소개

 

오늘 풀었던 피로도 - 프로그래머스 문제를 정리합니다.
이 문제는 유저의 남은 피로도를 기준으로, 가능한 던전 탐험 조합 중 가장 많은 던전을 도는 순서를 찾는 문제입니다.

핵심은 던전 순서를 바꿔 조합하며(순열) 조건을 검사합니다.

문제 링크: 피로도 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 던전 탐험 순서를 모두 탐색(순열)하여 경우의 수 확인
2. 각 순열에서 현재 피로도가 최소 필요 피로도 이상일 경우 탐험 가능
3. 모든 경우 중 최대 탐험 개수 기록

---

해결 과정 및 코드

핵심 아이디어

1. 던전은 최대 8개로, 8! = 40320가지 모든 경우의 수를 시도해도 무방함
2. 방문 여부를 체크하며 DFS으로 탐험 순서를 완전탐색
3. 현재 피로도가 해당 던전의 최소 필요 피로도보다 크거나 같을 경우만 진행
4. 각 재귀 호출에서 최대 탐험 횟수를 갱신

코드

시간 복잡도 :O(N!)
이유: 던전이 최대 8개 → 모든 순열 조합 탐색이므로 N!

 

import java.util.*;

class Solution {
    public int solution(int k, int[][] dungeons) {
        // 모든 순열을 탐색하며 최대 탐험 수를 반환
        return perm(k, 0, dungeons, new boolean[dungeons.length], 0);
    }
    
    // 재귀적으로 가능한 던전 순열을 완전 탐색
    private int perm(int curFatigue, int select, int[][] dungeons, boolean[] visited, int cnt) {
        int max = cnt;  // 현재까지 탐험한 던전 수를 기준으로 최대값 초기화

        for (int i = 0; i < dungeons.length; i++) {
            // 이미 방문한 던전은 스킵
            if (visited[i]) continue;

            // 현재 피로도가 최소 필요 피로도보다 작다면 탐험 불가
            if (curFatigue < dungeons[i][0]) continue;

            // 던전 탐험 시작
            visited[i] = true;
            // 피로도 감소, 탐험 수 증가
            max = Math.max(
                max,
                perm(curFatigue - dungeons[i][1], select + 1, dungeons, visited, cnt + 1)
            );
            // 탐험 완료 후 상태 복원
            visited[i] = false;
        }

        return max; // 현재 경우의 최대 탐험 수 반환
    }
}