99클럽 코테 스터디 22일차 TIL (87946번: 피로도)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=java

프로그래머스

---

학습 키워드

• 완전 탐색

 

풀이 및 코드

• DFS로 탐색하면서 탐색한다.
• 예를 들어 던전이 세 개 인 경우, 1 -> 2 -> 3 / 1 -> 3 -> 2 / 2 -> 1 -> 3 / 2 -> 3 -> 1 / 3 -> 1 -> 2 / 3 -> 2 -> 1 을 모두 찾아본다. 단, 최소 피로도가 부족한 경우에는 해당 던전에 들어가지 않게 해야한다.

import java.util.*;

class Solution {
    private static int answer = 0;
    
    public int solution(int k, int[][] dungeons) {
        Arrays.sort(dungeons, (a, b) -> {
            if (a[1] == b[1]) {
                return b[0] - a[0];
            }
            return a[1] - b[1];
        });
        boolean[] visited = new boolean[dungeons.length];
        dfs(k, dungeons, visited, 0, dungeons.length);
        return answer;
    }
    
    private static void dfs(int k, int[][] dungeons, boolean[] visited, int count, int remaind) {
        if (remaind == 0) {
            answer = Math.max(answer, count);
            return;
        }

        for (int r = 0; r < dungeons.length; r++) {
            int[] dungeon = dungeons[r];
            if (visited[r]) {
                continue;
            }
            visited[r] = true;
            if (k < dungeon[0]) {
                dfs(k, dungeons, visited, count, remaind - 1);
            } else {
                dfs(k - dungeon[1], dungeons, visited, count + 1, remaind - 1);
            }
            visited[r] = false;
        }
    }
}