🖊️ 문제

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

---

🖊️ 풀이

던전에 출입할 수 있는 조건은
1. 현재 남은 피로도 (k)가 던전의 최소 필요 피로도(dungeons[i][[0])보다 크거나 같고,
2. 아직 출입하지 않은 던전인 경우.

따라서 던전의 출입 여부를 visited 배열을 통해 관리하고,

위의 두 조건을 지키면서 전체 던전들을 탐색한다.

그래서 DFS를 통해서 풀어본댜.

idx를 통해 던전 출입 가능한 개수를 갱신해주면 된다.

DFS로 스택에 쌓인 재귀 호출들이 풀리면 새로 탐색해줘야 하니까 visited를 다시 false로 바꿔줘야 하는 것도 있음!

#include <string>
#include <vector>

using namespace std;

int total = -1;
bool visited[9] = {false, };

void DFS(int cur, int idx, vector<vector<int>>& dg) 
{
    if (idx > total) total = idx;
    for(int i = 0 ; i < dg.size() ; i++) {
        if (cur >= dg[i][0] && visited[i] == false) {
            visited[i] = true;
            DFS(cur - dg[i][1], idx + 1, dg);
            visited[i] = false;
        }
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    
    DFS(k, 0, dungeons);
    
    answer = total;
    
    return answer;
}