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

문제

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

코딩테스트 연습 - 피로도

문제풀이

 

완전탐색으로 문제를 풀었다.

visited벡터를 이용해 idx번째 던전을 방문했는지 판별을 한다.

 

방문을 하지 않은 던전이라면 해당 던전을 무시하고 다음 던전을 탐색하기 위해 DFS를 실행한다.

또는 해당 던전을 방문할 것이라면 현재 피로도가 던전의 최소 피로도 이상인지 확인을 하고 DFS를 실행한다.

 

모든 던전을 방문 했다면 answer값을 최댓값으로 갱신한다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>>dungeon;
vector<bool>visited;
int answer;

void DFS(int idx, int cnt, int fa) {
    if (idx == dungeon.size()) {
        answer = max(answer, cnt);
        return;
    }

    for (int idx2 = 0; idx2 < dungeon.size(); ++idx2) {        
        if (visited[idx2] == true) continue;
        visited[idx2] = true;
        
        DFS(idx + 1, cnt, fa);
        visited[idx2] = false;
        
        if (fa >= dungeon[idx2][0]) {
            visited[idx2] = true;
            DFS(idx + 1, cnt + 1, fa - dungeon[idx2][1]);
            visited[idx2] = false;
        }
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    dungeon = dungeons;
    visited = vector<bool>(dungeon.size(), false);
    DFS(0, 0, k);
    return answer;
}