완전탐색, dfs

문제를 풀다가,
재귀를 사용하여 dfs를 사용하는 부분이 완벽하게 정리된 것 같지 않아서 정리해본다.

본 문제는 모든 경우의 수를 고려하여 탐험 가능한 던전의 최대 갯수를 반환하는 문제였다.

#include <string>
#include <vector>
#define MAX 8

using namespace std;
// dfs 사용
int answer = 0;
bool visited[MAX] = {false};

void dfs(int cnt, int k, vector<vector<int>> &dungeons)
{
    if(cnt > answer) answer = cnt;
    
    for(int i=0; i<dungeons.size(); i++)
    {
        if(visited[i] == false && dungeons[i][0] <= k)
        {
            visited[i] = true; // 방문기록
            dfs(cnt+1, k-dungeons[i][1], dungeons); // 다음 탐색
            visited[i] = false; // 방금 탐색한 곳은 for문에 의한 재탐색을 위해 다시 미방문 기록
        }
    }
}

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

visited[]를 활용하여, 방문한 곳을 true, 방문하지 않은 곳을 false로 두고
다음 탐색을 위해
dfs재귀가 끝난 다음엔 true였던 visited[i] 를 다시 false로 바꿔두는 부분이 요점이었다.