프로그래머스 피로도

 

탐색에서 다시 돌아온다면 방문을 다시 false 로 만들어주자. 탐색 재귀 시에 그냥 인덱스 쪽에 + 1 만 해주면 되는 경우를 항상 생각하자. 던전의 방문 최대 횟수는 던전의 총 갯수 일 것이기 때문이다. 방문 불가 시 어짜피 다음 던전으로 이동한다.

 

또 k 의 값을 함수 내에서 변화를 주지 말자. 함수 구현부에서 변화를 주면 해당 반복문 동안 k의 값이 변해있어 문제 풀이가 어렵다. 아래 구문처럼 k를 매개변수로 넣을 때 - 해주자. 그럼 for 문에서 의 k 값에는 변화가 없지만 Dfs 에 재귀 되어질 k 값은 변화가 있다.

 

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> inDun;
vector<bool> visited = vector<bool>(8, false);
int answer = 0;
int Dfs(int index, int k)
{
    if(index > answer) answer = index;
    
    for(int i = 0; i< inDun.size(); ++i)
    {
        if(visited[i] == true)
            continue;
        if(inDun[i][0] > k)
            continue;
        visited[i] = true;
        Dfs(index + 1, k - inDun[i][1]);
        visited[i] = false;
    }
    return answer;
}

int solution(int k, vector<vector<int>> dungeons) {
   inDun = dungeons;
    Dfs(0, k);
    
    return answer;
}