[Programmers]#Level2_피로도, 완전 탐색, DFS, 깊이 우선 탐색, 백트래킹

 

#1. 문제

 

프로그래머스

 

---

 

#2. 풀이

 

1. 깊이 우선 탐색(그래프)

 

[자료구조]#6_그래프

 

깊이 우선 탐색은 그래프의 모든 정점을 탐색하는 방법 중 하나입니다. 깊이 우선 탐색은 출발 정점으로부터 더 이상 확장 불가능한 단말 노드까지 우선적으로 탐색하는 방법입니다. 일반적으로, DFS는 재귀 호출 혹은 스택 자료구조를 활용하여 구현합니다. 

 

2. 백트래킹

 

[알고리즘]#6_백 트래킹

 

백트래킹은 문제 해결을 위해 여러 후보 해결책들을 점진적으로 탐색하며, 현재 선택한 경로가 해결책으로 이어질 수 없다고 판단되면, 이전 단계로 돌아가서 다른 경로에 대한 탐색을 시도하는 알고리즘 기법입니다. 일반적으로, 백트래킹 알고리즘은 재귀호출을 활용한 DFS를 통해 구현하며, 탐색 과정에서 현재 경로/정점에 대한 조건 만족 여부를 검사하고, "return(이전 단계로 돌아갈지)" 혹은 깊이 우선 탐색을 계속 진행할지 결정하는 방식으로 동작합니다. *특히, 조합과 순열의 차이점을 고려해 순서와 중복 여부를 고려하고 알고리즘을 구현해야합니다!

 

3. 던전 이동에 제약이 없으니, 최소 피로도와 소모 피로도를 통해 조건을 작성하자!

 

1. 먼저, 한 던전으로부터 이동 가능한 다른 던전에 대한 제약이 없으니, 모든 던전을 출발 던전으로 설정하는 DFS를 구현합니다.
2. [조건 만족] : 현재 던전에서 다른 모든 던전들을 순회하며, 방문 여부+최소 피로도 충족 여부를 확인하여 해당 조건을 만족하는 다음 던전으로의 탐색을 계속 진행합니다. 백트래킹을 위해 다음 던전의 방문 여부를 true -> false로 변경하고, 다음 후보 던전들에 대한 탐색을 진행합니다.
3. [조건 불만족] :  만약, 현재 던전으로부터 더 이상의 탐색이 불가능하다고 판단되면, 현재까지 탐색한 던전 수를 통해 탐색 가능한 최대 던전 수를 갱신해 줍니다.

 

---

 

#3. 코드

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int maxDungeon;

void dfs(int leftFatigue, int cnt, const int &maxFatigue, vector<vector<int>> &dungeons,
         vector<bool> &visited)
{
    for (int i = 0; i < dungeons.size(); ++i)
    {
        if (!visited[i] && leftFatigue >= dungeons[i][0])
        {
            visited[i] = true;
            dfs(leftFatigue - dungeons[i][1], cnt + 1, maxFatigue, dungeons, visited);
            visited[i] = false;
        }
    }

    maxDungeon = max(maxDungeon, cnt);
}

int solution(int k, vector<vector<int>> dungeons)
{
    vector<bool> visited(dungeons.size(), false);

    dfs(k, 0, k, dungeons, visited);

    return maxDungeon;
}

 

 

---