*문제 출처는 프로그래머스에 있습니다.
문제 제목: 피로도 (2단계)
문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/87946
문제 설명
나의 풀이
#include <string>
#include <vector>
#define MAX 8
using namespace std;
int result = 0;
bool visited[MAX] = {false};
int dfs(int cnt, int k, vector<vector<int>> &dungeons) {
if (cnt > result) result = 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;
}
}
return result;
}
int solution(int k, vector<vector<int>> dungeons) {
int answer = -1;
answer = dfs(0, k, dungeons);
return answer;
}
위 코드의 작동 방식은 다음과 같다.
DFS 방식으로 풀었으며 DFS는 하나를 기점으로 잡고 모든 과정을 경우의 수를 탐색하고 다시 돌아오는 방식을 취했다.
※ 알아야 할 것
반복문 안에서 재귀함수를 사용하면 무한루프에 빠질 수 있다. 하지만 위 풀이에서는 탐색한 던전을 다시 들어가지 않기 위해서 bool형으로 들어갔던 방은 true로 만들었다. 그래서 무한루프에 빠지지 않았다.
반복문에서 재귀함수를 사용하면 반복문에 있는 i는 다시 0부터 시작한다.
'코딩테스트(프로그래머스 & 백준) > 프로그래머스-C++' 카테고리의 다른 글
Programmers / 주식가격 / C++ (1) | 2024.03.14 |
---|---|
Programmers / 타겟 넘버 / C++ (0) | 2024.03.12 |
Programmers / 분수의 덧셈 / C++ (0) | 2024.03.08 |
Programmers / 튜플 / C++ (0) | 2024.03.07 |
Programmers / 행렬의 곱셈 / C++ (0) | 2024.03.06 |