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

코딩테스트 연습 - 피로도 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool visited[8] = {false,};
int answer = 0;
void DFS(int k, vector<vector<int>> dungeons, int cnt)
{
    answer = max(answer, cnt);//깊이 갱신
    for (int i=0; i<dungeons.size(); i++) {
        if (!visited[i] && dungeons[i][0] <= k) {
            visited[i] = true;
            DFS(k - dungeons[i][1], dungeons, cnt + 1);
            visited[i] = false;
        }
    }
}
int solution(int k, vector<vector<int>> dungeons) {
    DFS(k, dungeons, 0);
    return answer;
}

DFS에도 많은 형태가 있지만 visited를 판단해야 하는 경우

보통 DFS의 요소 중 하나는 깊이를 지정해주고, 그 안의 DFS요소를 지정할 때는 새로 판단해야 하는 갱신되는 값, 배열 그대로, 깊이 (+1 ) 요런 식으로 많이 들고 있는다.

그리고 DFS안에 for문을 돌려 모든 요소를 참조해주는데, if문으로 visited를 판단해주어야 하며, 방문하지 않았을 경우 들어가서 visited를 true로 만들어준 후 DFS를 재귀로 불러주고, 그 DFS를 모두 선언했을때 visited를 false로 해주어야 함.

 

visited를 false로 해주어야 하는 이유: 맨 첫번째 깊이에서 for문을 따졌을 때, i = 0에 대해 깊이를 끝까지 들어갔으면 i = 1를 시작할때 visited가 처음 들어가는 것처럼 다시 전부 false로 세팅되어있어야 함.(BFS와는 다른 DFS만의 특징)

그림으로 나타내면 이렇다.

숫자: 갱신되는 k의 값 / 빨간 글씨: 요소 index(visited) / 연두 글씨: dfs가 실행되는 순서 (for + if문에 의한) / 0123 ==> 깊이(cnt)

 

 

 

문제 팁)

사실 DFS뿐만이 아니라 next_permutation같은 순열로 풀어도 되고(배열길이가 8이 최대이므로)

BFS로 푸는것이 더 시간복잡도가 적긴 할 것임.. BFS를 더공부할 필요가 있어보인다.

---

 

번외) 2차원 vector 두번째 원소 기준으로 정렬

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

bool cmp(vector<int> &v1, vector<int> &v2){
  if(v1[1] == v2[1])
    return v1[0]<v2[0];
  else return v1[1]<v2[1];
}

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    sort(dungeons.begin(), dungeons.end(), cmp);
    for(int i = 0; i < dungeons.size();i++)
        cout << dungeons[i][0] <<"," <<dungeons[i][1] << endl;
    return answer;
}