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

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

프로그래머스

 

cpp

닫기 줄바꿈

#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 프로그래머스 소스코드