[프로그래머스] 피로도 (완전탐색 Lv. 2) - 자바 Java

문제

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

풀이

dfs (백트랙킹)

import java.util.*;

class Solution {
    public static boolean[] visit;
    public static int answer = Integer.MIN_VALUE;

    public int solution(int k, int[][] dungeons) {

        visit = new boolean[dungeons.length];


        dfs(0, 0, k, dungeons);

        return answer;
    }

    public static void dfs(int cnt, int depth, int k, int[][] dungeons) {

        if (answer < cnt) {
            answer = cnt;
        }
        for (int i = 0; i < dungeons.length; i++) {
            if (!visit[i] && k >= dungeons[i][0]) {
                visit[i] = true;
                dfs(cnt + 1, depth + 1, k - dungeons[i][1], dungeons);
                visit[i] = false;
            }
        }

    }
}