Programmers / 피로도 / C++

*문제 출처는 프로그래머스에 있습니다.

 

문제 제목: 피로도 (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;
}

 

위 코드의 작동 방식은 다음과 같다.

 

O = 들어갈 수 있는 던전 / X = 못 들어가는 던전이다.

 

DFS 방식으로 풀었으며 DFS는 하나를 기점으로 잡고 모든 과정을 경우의 수를 탐색하고 다시 돌아오는 방식을 취했다.

---

※ 알아야 할 것

 

반복문 안에서 재귀함수를 사용하면 무한루프에 빠질 수 있다. 하지만 위 풀이에서는 탐색한 던전을 다시 들어가지 않기 위해서 bool형으로 들어갔던 방은 true로 만들었다. 그래서 무한루프에 빠지지 않았다.

반복문에서 재귀함수를 사용하면 반복문에 있는 i는 다시 0부터 시작한다.