프로그래머스, C++) Lv 2. 피로도

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=cpp

프로그래머스

 

기존의 dfs와 동일하나 백트레킹이라는 개념이 추가됨

dfs의 경우, visited배열을 통해 갔던 곳을 안가게 함.

그러나 '피로도'의 경우, 가능한 모든 경우의 수를 전부 체크하기 때문에 재귀가 끝난 후, 다시 visited[i] = false 처리를 통해 모든 경우의 수 탐색

 

dfs와 재귀 기반의 코드 

#include <bits/stdc++.h>
using namespace std;

int answer = 0;

void dfs(int fatigue, const vector<vector<int>>& dungeons, vector<bool>& visited, int count) {
    answer = max(answer, count);

    for (int i = 0; i < dungeons.size(); ++i) {
        if (visited[i]) continue; // 이미 방문한 던전이면 넘어감

        int need = dungeons[i][0]; // 최소 필요 피로도
        int cost = dungeons[i][1]; // 소모 피로도

        if (fatigue >= need) {
            visited[i] = true; // 방문 표시
            dfs(fatigue - cost, dungeons, visited, count + 1);
            visited[i] = false; // 백트래킹 (원상복구)
        }
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    vector<bool> visited(dungeons.size(), false);
    dfs(k, dungeons, visited, 0);
    return answer;
}