[프로그래머스] 2단계 - 피로도

문제 설명

유저가 탐험 할 수 있는 최대 던전 수를 return

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

프로그래머스

 

문제 풀이법

만약 던전이 3개가 있다면 갈 수 있는 던전들은 123, 132, 213, 231, 312, 321이 있으므로 dfs를 통해 문제를 풀었다

 

dfs 메소드의 cnt는 현재 간 던전의 수이고, k는 현재 피로도이다

answer는 현재 간 던전의 수의 max값으로 매번 갱신한다

 

그리고 던전의 갯수만큼 for문을 돌면서 재귀를 돌아준다

재귀를 돌때는 현재 피로도를 계산해서 돌아주어야한다

이때 재귀를 돌때 방문했는지의 여부와 남은 피로도를 잘 계산해주면서 재귀를 돌 수 있도록 해야한다

 

 

소스 코드

#include <string>
#include <vector>

using namespace std;

int visited[9] = { 0 };
int answer = -1;

void dfs(int cnt, int k, vector<vector<int>> dungeons) {
    answer = max(answer, cnt);
    
    for (int i = 0; i < dungeons.size(); i++) {
        if (visited[i] == 0 && k >= dungeons[i][0]) {
            visited[i] = 1;
            dfs(cnt + 1, k - dungeons[i][1], dungeons);
            visited[i] = 0;
        }
    }
    
}

int solution(int k, vector<vector<int>> dungeons) {
    dfs(0, k, dungeons);
    
    return answer;
}