[Java] 2021 위클리 챌린지 12주차 - 피로도

던전의 개수가 8개로 수가 많지 않다.

던전을 탐험하는 경우의 수는 8! 인데, 이는 작은 숫자이므로 Brute force로 해결이 가능하다.

순열을 찾는 알고리즘은 back tracking을 사용할 수 있는데, 던전을 방문하고 함수를 탐색을 하고 탐색이 끝나면 방문 내역에서 지워주면 된다.

import java.util.HashSet;
import java.util.Set;

class Solution {
    Set<String> visited = new HashSet<>();
    int answer = 0;
    public String makeKey(int[] d){
        return d[0] + "&" + d[1];
    }
    public void solve(int k, int[][] dungeons, int depth){
        int n = dungeons.length;
        answer = Math.max(depth, answer);
        for(int i = 0; i < n; i ++){
            int[] d = dungeons[i];
            String key = makeKey(d);
            if(!visited.contains(key) && k >= d[0]){
                visited.add(key);
                solve(k - d[1], dungeons, depth + 1);
                visited.remove(key);
            }
        }
    }
    public int solution(int k, int[][] dungeons) {
        solve(k, dungeons, 0);
        return answer;
    }
}