프로그래머스 87946 C++ [피로도]

// DFS를 이용한 풀이
#include <bits/stdc++.h>
using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    vector<bool> visited(dungeons.size(), false);
    auto dfs = [&](auto &self, int cur_k, int cnt) -> void {
        answer = max(answer, cnt);  // 매 탐색마다 최댓값 갱신
        for (size_t i = 0; i < dungeons.size(); ++i) {
            // 현재 남은 피로도가 탐색한 던전의 최소 필요 피로도 이상이고
            // 아직 해당 던전을 방문하지 않은 경우
            if (cur_k >= dungeons[i][0] && !visited[i]) {
                visited[i] = true;  // 방문 표시
                self(self, cur_k - dungeons[i][1], cnt + 1);  // 현재 남은 필요도에서 해당 던전의 소모 필요도를 차감하고 방문 카운트를 하고 재귀 호출
                visited[i] = false;  // 방문 표시 해제
            }
        }
    };
    dfs(dfs, k, 0);
    return answer;
}