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

프로그래머스 : 피로도 (Java)

문제

문제 확인하기

풀이

던전의 최대 개수는 8개이다.

던전의 개수가 최대, 즉, 8개일 때, 모든 던전을 탐험하는 경우의 수는 8!으로 40320개이다.
따라서 완전 탐색으로 정답을 찾을 수 있다.

완전 탐색을 위해 DFS를 이용하였다.

모든 경로를 탐색해보기 위해 DFS 메서드 내에서 반복문을 이용했다.

남은 피로도로 현재 던전을 탐험할 수 있다면 해당 던전을 탐험처리하고 다음 던전을 선택하도록 한다.
반복을 통해 가능한 모든 경로를 탐험한다.

문제에서 요구하는 것은 유저가 탐험할 수 있는 최대 던전의 수이다.
DFS 메서드는 탐험 가능한 최대 던전의 수를 반환해야 한다.

DFS 메서드가 현재 탐험 가능한 던전의 수를 반환하도록 하면, 가장 깊은 곳의 DFS 메서드는 탐험할 수 있는 던전이 없을 것이다.
따라서 가장 깊은 곳의 DFS 메서드는 0을 반환한다.
가장 깊은 곳 이전의 DFS 메서드는, 가장 깊은 DFS 메서드를 호출 했기 때문에 하나의 던전을 탐험할 수 있는 상태다.
이를 이용하면 현재 탐색하고 있는 경우의 탐험 가능한 던전의 수는 1 + dfs()이다.

반복을 통해 모든 경우를 탐색하므로, 탐험 가능한 던전의 수를 기록해두고 이를 비교하여, 가장 큰 값을 반환하도록 한다.

자바로 작성한 문제 해결 코드는 다음과 같다.

public class Solution {
    public int solution(int k, int[][] dungeons) {
        // dungeons[k][0] : 최소 필요 피로도
        // dungeons[k][1] : 소모 피로도
        return dfs(k, dungeons);
    }

    private int dfs(int remain, int[][] dungeons) {
        int count = 0;
        for (int[] arr : dungeons) {
            int required = arr[0], consumed = arr[1];
            if (remain >= arr[0]) {
                // 방문 처리
                arr[0] = 9999;
                // 더 큰 값 저장
                count = Math.max(count, 1 + dfs(remain - consumed, dungeons));
                // 방문 처리 원상 복귀
                arr[0] = required;
            }
        }
        // 어느 곳도 방문할 수 없다면 0 반환
        return count;
    }
}

방문 처리를 위해 visited 배열을 따로 두지 않았다.
DFS는 깊이 우선 탐색이기 때문에, dungeons 배열의 최소 필요 피로도를 변경하여 방문 처리를 할 수 있다.
해당 경로를 탐색한 후에는 변경한 최소 필요 피로도를 원상 복귀해주면 된다.

최소 필요 피로도를 변경해도, 해당 경로 탐색을 마쳐야 다른 경로를 탐색하기 때문에 다른 경로의 탐색에 영향을 미치지 않는다.