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

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

프로그래머스

dfs 문제다.

방문했는지 체크하는 check 배열로 아직 방문하지 않았으면서

최소 필요도를 충족하는 던전에 대해 dfs를 호출한다.

#include <string>
#include <vector>
using namespace std;

int answer = -1;
void dfs(int k, vector<vector<int>> dungeons, vector<int>check,int cnt)
{
    for(int i=0;i<check.size();i++)
    {
        if(!check[i])
        {
            check[i]=1;
            if(dungeons[i][0]<=k)//방문 가능하다면
                dfs(k-dungeons[i][1],dungeons,check,cnt+1);
            //다른 순서도 따져봐야하므로 다시 0으로 변경
            check[i]=0;
        }
    }
    if(cnt>answer)
        answer=cnt;
    
}

int solution(int k, vector<vector<int>> dungeons) {
    vector<int> check(dungeons.size(),0);//방문시 1로 변경
    dfs(k, dungeons, check,0);
    return answer;
}