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

문제

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

프로그래머스

풀이

dfs 문제

던전을 전보다 더 많이 탐색할 경우 answer을 갱신해준다.

만약 던전을 모두 돌 방법을 찾아서 answer이 던전 개수와 같다면 더 볼 필요 없으니 return

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

vector<int>visit;
int answer=0;

void dfs(int index,int tired,int cnt,vector<vector<int>>dungeons)
{
    if(answer<cnt){answer=cnt;}
    if(answer==dungeons.size()){return;}
    
    for(int i=0;i<dungeons.size();i++)
    {
        if(index==i||visit[i]!=0||tired<dungeons[i][0]) continue;
        visit[i]=1;
        dfs(i,tired-dungeons[i][1],cnt+1,dungeons);
        visit[i]=0;
    }
    return;
}

int solution(int k, vector<vector<int>> dungeons) 
{
    visit=vector<int>(k,0);
    
    for(int i=0;i<dungeons.size();i++)
    { dfs(i,k,0,dungeons); }
    
    return answer;
}