[프로그래머스] Lv2. 피로도

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

프로그래머스

 

dfs를 사용해서 탐험할 순서를 전부 완전탐색해주었다.

지정해놓은 순서를 탐험할때, 각 순서마다 탐험할 수 있는 동굴의 갯수를 카운팅 해주고, 기존의 최댓값보다 큰 경우 갱신해주는 방식으로 구현하였다. dfs로 순열을 구하는 방법을 잘 복기 시켜야겠다.

 

풀이 코드

import java.util.*;

class Solution {
    
    public static int answer;
    
    public int solution(int k, int[][] dungeons) {
        answer = -1;
        
        int n = dungeons.length;
        boolean[] visited = new boolean[n];
        int[] output = new int[n];
        
        dfs(n, 0, output, visited, dungeons, k);
        
        return answer;
    }
    
    public void dfs(int n, int depth, int[] output, boolean[]visited, int[][] dungeons, int k) {
        if(depth == n) { // 각각의 짝에 맞게
            
            int cnt = 0;
            
            for(int i = 0; i < output.length; i++) { // 탐험 가능 한지 비교
                int minTired = dungeons[output[i]][0];
                int minusTired = dungeons[output[i]][1];
                
                if(minTired <= k) {
                    cnt++;
                    k -= minusTired;
                }else { // 체력 안되면 나가리
                    break;
                }
            }
            answer = Math.max(answer, cnt);
        }
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                output[depth] = i;
                visited[i] = true;
                dfs(n, depth+1, output, visited, dungeons, k);
                visited[i] = false;
            }
        }
    }
    
}