프로그래머스(완전탐색; 피로도) c++

#include <string>
#include <vector>

using namespace std;

int maxCount = 0;
bool bvisited[8] = {false, };

void dfs(int currHealth, vector<vector<int>> dungeons, int count)
{
    maxCount = maxCount < count ? count : maxCount;

    for(int i = 0; i < dungeons.size(); ++i)
    {
        if(bvisited[i]) continue;
        
        int need = dungeons[i][0];          // 입장료
        int cost = dungeons[i][1];          // 소모량
        
        if (currHealth < need) continue;             // 입밴
        
        bvisited[i] = true;
        dfs(currHealth-cost, dungeons, count+1);
        bvisited[i] = false;                // 다음을 위해 원상복구
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    dfs(k, dungeons, 0);
    return maxCount;
}

 

해설:

전역필드로 maxCount, bvisited을 선언해준다. maxCount는 입장횟수이며 bvisited는 탐색 중복 방지이다.

[[80,20],[50,40],[30,10]] 던전 배열은 이렇게 주어지므로 dungeons[i][0] = 입장료, dungeons[i][1] 피로도로 접근한다.

 

첫번째: 반복몬을 통해 던전 배열에 접근하고 위에 방법을 통해 입장료와 피로도 정의한다. 이후 조건문을 통해 현재체력(currHealth)가 입장료보다 적으면 넘긴다.

두번째: 조건문을 통가하면 bvisted에 true로 설정하여 중복 탐색을 방지하고 dfs특성으로 재귀적으로 현재체력 - 소모량, 던전배열, count + 1 방식으로 호출하여 탐색을 시작한다.

!!!!count에서 입밴 조건문을 통과하지 못하면 count 증가를 못하므로 maxCount가 업데이트 되지 않아 최댓값으로 찍힌다.!!!