[프로그래머스 / Java] Lv.2 피로도 (업데이트 중..)

Question

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

프로그래머스

---

Algorithm

1.  

---

Code

class Solution {
    // 최대 탐험 가능한 던전 수를 저장하는 변수
    static int answer = 0;

    // 각 던전을 방문했는지 여부를 체크하는 배열
    static boolean[] check;

    public int solution(int k, int[][] dungeons) {
        // 던전 개수만큼 방문 체크 배열 생성
        check = new boolean[dungeons.length];

        // DFS 시작 (현재 피로도 k, 깊이 0부터 시작)
        DFS(k, dungeons, 0);

        // 최종적으로 최대 탐험 가능한 던전 수 반환
        return answer;
    }

    // DFS(깊이 우선 탐색)
    // k : 현재 남은 피로도
    // d : 던전 정보 배열
    // deep : 현재까지 탐험한 던전 수
    public void DFS(int k, int[][] d, int deep) {

        // 현재까지 탐험한 던전 수 중 최대값 갱신
        answer = Math.max(answer, deep);

        // 모든 던전을 하나씩 확인
        for(int i = 0; i < d.length; i++) {

            // 아직 방문하지 않았고, 최소 필요 피로도를 만족하면
            if(!check[i] && k >= d[i][0]) {

                // 해당 던전을 방문 처리
                check[i] = true;

                // 피로도를 소모하고 다음 단계로 DFS 진행
                DFS(k - d[i][1], d, deep + 1);

                // 백트래킹: 다른 경우의 수를 위해 방문 해제
                check[i] = false;
            }
        }
    }
}

---

시간 복잡도

• 던전의 개수를 n이라 하면 가능한 모든 순열을 탐색하므로 최악의 경우 O(n!)
• 문제 조건에서
  • n ≤ 8
  • 최대 경우의 수: 8! = 40,320

➡️ 완전탐색이지만 입력 크기가 작아 충분히 가능