99클럽 코딩 테스트 22일차 TIL

프로그래머스 - 피로도

n번 던전부터 탐험을 시작했을 때 나올 수 있는 최대 던전 수를 구해야 한다.

첫 번째 던전을 탐험하고 남은 피로도를 바탕으로 나머지 던전을 탐험해야 한다.

던전을 탐험할 수 있는 모든 루트를 계산해야하기 때문에 DFS 가 사용된다.

구현

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

        dfs(0, k, dungeons);

        return result;
    }

    void dfs(int depth, int fatigue, int[][] dg) {
        for (int i = 0; i < dg.length; i++) {
            if (!visited[i] && dg[i][0] <= fatigue) {
                visited[i] = true;
                dfs(depth + 1, fatigue - dg[i][1], dg);
                visited[i] = false; // 다른 던전부터 탐험하는 경우도 있기 때문에 방문 초기화
            }
        }

        result = Math.max(result, depth);
    }

}

---

프로그래머스 - 피로도

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