프로그래머스 - 피로도

완전탐색(Brute Force) : 모든 경우의 수를 시도하여 정답을 찾는 방법. 상대적으로 간단한 방법이지만 경우의 수가 많아지면 시간이 오래걸린다.

완전탐색의 종류
1. 단순 Brute-Force
2. 비트마스크(Bitmask)
3. 재귀함수
4. 순열

// 재귀함수를 이용
public class Test_29_Fatigue {
    private int maxDungeons = 0; // 들어갈 수 있는 최대 던전 수

    public int solution(int k, int[][] dungeons) {
        boolean[] visited = new boolean[dungeons.length]; // 던전의 방문 여부
        explore(k, dungeons, visited, 0); // 재귀함수 호출
        
        return maxDungeons;
    }

    private void explore(int k, int[][] dungeons, boolean[] visited, int count) {
        // 모든 던전 반복
        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && k >= dungeons[i][0]) { // 던전 입장이 가능하고, 최소 피로도가 남은 경우
                visited[i] = true; // 방문으로 표시
                explore(k - dungeons[i][1], dungeons, visited, count + 1); // 남은 피로도를 계산해서 재귀함수 호출
                visited[i] = false; // 백트래킹을 위해 미방문 상태로 변경
            }
        }
        // 최대 던전 수 갱신
        maxDungeons = Math.max(maxDungeons, count);
    }
}