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

프로그래머스

접근 방식

모든 던전을 탐색하면서 던전 진입이 가능한지 여부(최소 피로도를 충족하는가)를 체크하고, 그에 따라 발생하는 두 가지 선택지를 고려해야하는 문제이다. 두 가지 선택지는 다음과 같다:

  1) 최소 피로도 충족: 던전에 진입해 던전을 탐험 후 소모피로도를 감소시킨 후에 다음 던전을 탐험

  2) 최소 피로도 미충족: 현재까지의 탐험 횟수와 최대 탐험 횟수(max)를 비교하여 큰 쪽을 최대 탐험횟수로 변경

이러한 접근 방식을 고려하면 모든 경우의 수를 탐색해야하는데, 던전의 개수가 8개 이하이기 때문에 DFS로 접근하여 문제를 해결했다. 또한 한 번 방문한 던전을 재방문하지 않도록 visited[] 배열을 선언하여 방문여부를 체크했다.

로직 설명

- 방문여부를 체크할 배열 int[] visited 선언

- explore 메서드 내부:

  1) 모든 던전에 대해 반복문 실행 (이번 던전을 방문한 적이 없고 던전의 최소 피로도가 k를 넘지 않을때만 실행)

  2) 던전의 방문여부 1로 변경, 소모피로도를 k에서 뺀 후 explore() 메서드 다시 실행, 방문여부 0으로 변경

    -> 방문여부를 다시 0으로 만드는 이유는 이전 회차의 방문여부가 다음 회차에 영향을 주게 하지 않기 위함 

  3) 모든 탐험을 마치고 나서 count를 max와 비교하여 더 큰 쪽을 max로 변경

  4) max값 반환 

class Solution {
    public int solution(int k, int[][] dungeons) {
        int[] visited = new int[dungeons.length];
        explore(dungeons, visited, k, 0);
        
        return max;  
    }
    
    private int max = 0;
    
    private void explore(int[][] dungeons, int[] visited, int k, int count){
        for(int i = 0; i < dungeons.length; i++){
            if(visited[i] == 0 && k >= dungeons[i][0]){
                visited[i] = 1;
                explore(dungeons, visited, k - dungeons[i][1], count + 1);
                visited[i] = 0;
            }
        }     
        
        if(max < count){
            max = count;
        }
    }
}