[프로그래머스/C++] 피로도

(7/22 - 세모) 푸는 데 1시간이나 걸렸음

 

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

프로그래머스

 

구현

dfs로 입장 가능한 모든 던전을 탐색하고, 가장 높은 depth를 가졌을 때의 수를 세서 반환한다.

 

 

실수

dfs도 완전 탐색의 일부구나.. 완전 탐색이라는 건 brute force만 해당되는 줄 알았다..!

 

코드

#include <string>
#include <vector>

using namespace std;

bool visited[9];
int max_cnt;
void dfs(int cur, int pirodo, vector<vector<int>>& ds, int size, int cnt) {
    if (pirodo < ds[cur][0]) { // 피로도가 최소 피로도보다 낮음, 진입 불가
        return;
    }

    // 던전 입장
    pirodo -= ds[cur][1];
    visited[cur] = true;


    for (int i = 0; i < size; i++) {
        if (visited[i] == true) continue;
        dfs(i, pirodo, ds, size, cnt + 1);
    }

    // 더 돌 수 있는 던전 없음
    max_cnt = max(max_cnt, cnt);

    visited[cur] = false;
}


int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;

    int pirodo = k;
    int size = dungeons.size();
    
    for (int i = 0; i < size; i++) {
        dfs(i, pirodo, dungeons, size, 1);
    }
    answer = max_cnt;
    return answer;
}