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

 

 

 

 

 

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

프로그래머스

 

이번 문제는 dfs 문제였습니다.

 

 

 

 

 

📝 문제 풀이

1. 탐험한 던전 수를 0으로 시작하여 dfs 수행

2. 탐험하지 않은 던전이고 해당 던전의 최소 필요 피로도가 k보다 작거나 같으면 해당 던전 탐험 (dfs 수행)

3. dfs 수행이 끝난 던전은 다른 경우에서 재탐험할 수 있도록 방문 체크 해제 visited[i] = false

3. 현재 탐험 던전 수가 이전 탐험 던전 수보다 크면 cnt 갱신 answer = cnt

 

 

 

 

👩🏻‍💻 C++ 코드

#include <string>
#include <vector>
#define MAX 8

using namespace std;

int answer = 0;
bool visited[MAX] = {0};

void dfs(int cnt, int k, vector<vector<int>> &dungeons) {
    if (cnt > answer) answer = cnt;
    
    for (int i=0; i<dungeons.size(); i++) {
        if (!visited[i] && dungeons[i][0] <= k) {
            visited[i] = true;
            dfs(cnt + 1, k - dungeons[i][1], dungeons);
            visited[i] = false;
        }
    }
}

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

 

프로그래머스 - 결과 화면