[Programmers] (완전탐색) Lv 2. 피로도

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

int dfs(int& k, vector<vector<int>>& dungeons, int idx, int answer, vector<bool>& visit)
{
    k -= dungeons[idx].back(), visit[idx] = true;

    int res = answer;
    if (answer == dungeons.size())
        return res;
    
    for (int i = 0; i < dungeons.size(); ++i)
    {
        if (visit[i] || k < dungeons[i].front()) continue;

        res = max(dfs(k, dungeons, i, answer + 1, visit), res);
        k += dungeons[i].back(), visit[i] = false;
    }
    
    return res;
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer = 0, origin = k;
    vector<bool> visit(dungeons.size(), false);

    for (int i = 0; i < dungeons.size(); ++i)
    {
        answer = max(dfs(k, dungeons, i, 1, visit), answer);
        k = origin, visit[i] = false;
    }

    return answer;
}

GitHub : https://github.com/developeSHG/Algorithm-Baekjoon_Programmers/blob/b2e020cd3e915b20b4dddf40dad565209954067b/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/lv2/87946.%E2%80%85%ED%94%BC%EB%A1%9C%EB%8F%84/%ED%94%BC%EB%A1%9C%EB%8F%84.cpp

GitHub - developeSHG/Algorithm-Baekjoon_Programmers: 백준 and 프로그래머스 소스코드