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

현재 피로도에 따라서 최대로 탐험할 수 있는 던전의 수를 구하는 문제이다.

던전 탐험에 필요한 피로도가 2차원 배열로 주어지고, 던전 탐험 순서에 따라서 탐험할 수 있는 던전의 개수가 달라질 수 있으므로 백트래킹을 사용한 완전 탐색으로 구현했다.

 

매 dfs 호출마다 지금까지 탐험한 던전의 최대 갯수를 갱신해준다. (cnt는 매개변수로 가지고 있다.)

answer = max(answer, cnt);

 

현재 던전에서 다음 던전으로 이동하는 부분이다.

주의할 점은 다음 던전으로 이동하기 위해서 현재 피로도가 다음 던전에 필요한 피로도보다 많아야 한다는 점이다.

for(int i = 0; i < dungeons.size(); i++){
    if(visited[i]) continue;
    if(nowHp < dungeons[i][0]) continue;

    visited[i] = true;
    dunNum.push_back(i);
    dfs(cnt+1, nowHp - dungeons[i][1], dungeons);
    dunNum.push_back(i);
    visited[i] = false;
}

 

 

최종 코드

#include <string>
#include <vector>
#include <cstring>

using namespace std;

vector<int> dunNum;
bool visited[10];
int answer = 0;
void dfs(int cnt, int nowHp, vector<vector<int>> &dungeons){
    answer = max(answer, cnt);
    if(cnt == dungeons.size()){
        return;
    }
    
    for(int i = 0; i < dungeons.size(); i++){
        if(visited[i]) continue;
        if(nowHp < dungeons[i][0]) continue;
        
        visited[i] = true;
        dunNum.push_back(i);
        dfs(cnt+1, nowHp - dungeons[i][1], dungeons);
        dunNum.push_back(i);
        visited[i] = false;
    }
    
}

int solution(int k, vector<vector<int>> dungeons) {
    memset(visited, 0, sizeof(visited));
    dfs(0, k, dungeons);
    
    return answer;
}