[Java] 프로그래머스(level-2) - 피로도

문제 풀이

---

이 문제는 DFS 재귀함수를 활용하여 풀 수 있다.

아이디어 도출

먼저 재귀함수 안에서 던전 배열 dungeons를 순회하면서 방문한 던전인지 확인한다. 그리고 방문한 던전이라면 스킵하고 다음 던전을 탐색한다. 이떄, 각 던전에 최소 피로도와 소모 피로도를 비교하여 던전 탐색 여부를 결정한다.

탐색할 수 있는 던전이라면 아래와 같은 점화식을 처리하게 된다.

• 해당 던전을 방문한 것으로 처리한다.
• 다음 던전으로 재귀 호출할 때, 현재 피로도에서 소모될 피로도를 감소시켜서 재귀 호출한다.
• 해당 던전을 방문하지 않은 것으로 처리한다.

여기서 중요한 점은 DFS 재귀를 통해 방문 여부를 체크할 때 단순히 방문한 던전을 스킵하도록 하면 모든 경우의 수를 탐색할 수 없다는 점을 유의해야 한다는 것이다.

결국, 재귀 함수가 실행되는 흐름 안에서 모든 던전을 탐색하며 최소 피로도 조건을 충족했을 때 탐색까지 깊어진 재귀 횟수가 던전 탐험 횟수가 된다.

위 아이디어를 통해 작성한 코드는 아래와 같다.

작성 코드

---

import java.util.*;

class Solution {
    static int answer = 0;
    static boolean[] visited;

    public int solution(int k, int[][] dungeons) {
        // 방문 배열 초기화
        visited = new boolean[dungeons.length];
        // 첫번째 던전부터 DFS 재귀함수 호출
        DFS(0, k, dungeons);
        return answer;
    }
    static void DFS(int depth, int k, int[][] dungeons) {
        // 각 던전마다 탐험할 수 있는 던전인지 확인하여 DFS 재귀함수 호출
        for(int i=0; i<dungeons.length; i++) {
            if(!visited[i] && k>=dungeons[i][0]) {
                visited[i] = true;
                DFS(depth+1, k-dungeons[i][1], dungeons);
                // DFS 재귀함수 호출 후 해당 던전 방문 여부를 해제해주어야 한다.
                // 탐색하지 않은 던전이 있을 수 있기에 모든 던전을 탐색할 수 있도록 방문할 수 있도록 해주어야 한다. 
                visited[i] = false;
            }
        }
        answer = Math.max(answer, depth);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        int k =  80;
        int[][] dungeons = new int[][]{{80,20},{50,40},{30,10}};

        sol.solution(k, dungeons);
    }
}

회고

• ---

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.