Programmers_Level2_피로도

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

프로그래머스

 

---

 

 

우선 깊이 우선 탐색 (DFS : Depth First Search)로 모든 던전을 돌아다닌다. 

Depth를 비교하여 Depth가 깊다 == 많은 던전을 방문했다로 하였다. 

 

부모님끼리 친하셔서 어쩔 수 없이 알게된 사이라서 이름만 알고 어색한 사이같은 재귀를 사용하였는데 

Depth를 비교하기 위한 result 와 answer 변수를 재귀 함수 안에서 선언하고 초기화 하였고

그리고 방문한 던전의 확인을 위한 백터 또한 매개변수로 받도록 하였다. 

 

이렇게 코드를 짜고 실행해보니 반밖에 맞지 않는다.. ㅎㅎ 

 

오답 노트 (52.6점 코드)

#include <string>
#include <vector>

using namespace std; 


int DFS(int depth, int remain, vector<vector<int>>& dungeons, vector<bool>& isChecked)
{
    // for문에서 이미 dungeons의 사이즈만큼 순회하고 있기 때문에 의미 없는 if문..1 
    // 남은 피로도를 이미 for문 안에서 확인하고 있기 때문에 의미 없는 if문..2
    if(depth >= dungeons.size() || remain <= 0)
    {
        return depth; 
    }
    
	// 재귀 함수를 호출 할 때마다 초기화 된다
    int result = 0;
    int answer = 0;
    
    // 각 던전의 최소 필요 피로도에 대한 체크가 없기 때문에
    // 결국 모든 던전을 방문하게 된다. 최종 depth의 값 또한 던전의 길이로 고정이 될 것이다. 
    for(int idx = 0; idx < dungeons.size(); ++idx)
    {
        if(isChecked[idx]) continue;
        
        // 현재 방문한 던전의 소모 피로도를 차감했을 때 0일 경우 해당 던전까지 방문 가능하나
        // -값이 될 경우 해당 던전은 방문할 수 없다. 
        // 그런데 여기 if문에서는 두개를 구분하지 않고 현재의 depth를 반환하게 된다. 
        if(remain - dungeons[idx][1] <= 0)
        {
            return depth;
        }
        
        isChecked[idx] = true;
        
        result = DFS(depth + 1, remain - dungeons[idx][1], dungeons, isChecked);
        answer = result > answer ? result : answer; 
        
        isChecked[idx] = false;
    }
    
    return answer;
}


int solution(int k, vector<vector<int>> dungeons) {
    vector<bool> isChecked (8, false);
    
    return DFS(0, k, dungeons, isChecked);
}

 

 

내가 스스로 생각했을 때 실수한 부분은 다음과 같다. 

 

첫번째는 depth를 저정하고 비교하는 변수를 재귀 함수 내부에서 선언하고 초기화한 것. 

깊이 탐색을 해가면서 결과 값을 저장해야하는 변수를 굳-이 재귀 함수 안에서 선언해서 자원 낭비

 

두번째는 필요없는 if문이 존재하는 것. 

for문에서 확인 하는 내용을 if문이 다시 확인하게 된 것

 

세번째는 필요없는 parameter가 있다는 것. 

계속해서 공유하게되는 내용을 굳-이 함수의 매개변수로 전달한 것. 

 

네번째는 가장 근본적으로... 방문할 던전의 최소 필요 피로도를 확인하지 않았다는 것. 

결국엔 모든 던전을 방문하게 된다.. 

 

재귀 함수에서 이것저것 넣는 것이 아니라 문제를 최대한 담백하게 만드는 것이 필요하다. 

함수 내부에서 확인할 것은. 

1. 현재 Depth가 가장 깊은지? (가장 많은 던전을 방문 하였는지) 
2. 현재 남은 피로도가 이제 방문 할 던전의 최소 필요도 보다 많은지? (던전을 방문 할 수 있는지) 

두가지만 확인하면 굳이 이것저것 if문을 넣어가며 할 필요가 없었다. 

 

 

코드를 조금 더 다듬어서 결국 100점은 맞았다. 

재귀 함수를 이용한 완전탐색이 바로 머리에 떠오르지 않아서 계속 연습해야겠다.. 

 

재귀야! 이제는 어색해하지말고 좀 더 친해지자!! 

 

정답 코드 (좌) vs 오답 코드 (우)

 

 

정답 코드 100점

#include <string>
#include <vector>

using namespace std; 

// 정답을 위한 전역 변수
int answer = 0;
// 방문한 인덱스를 확인하기 위한 백터
vector<bool> isChecked (8, false);

// 던전의 정보를 참조 전달받아 재귀함수를 실행함
void DFS(int depth, int remain, vector<vector<int>>& dungeons)
{    
	// 삼항연산자로 현재 depth와 지금까지 가장 깊은 depth를 비교
    answer = depth > answer ? depth : answer;

    for(int idx = 0; idx < dungeons.size(); ++idx)
    {
    	// 이미 확인한 인덱스라면 넘어감
        if(isChecked[idx]) continue;
        
        // 남은 피로도와 최소 필요 피로도와 비교, 작다면 못가는 던전
        if(remain < dungeons[idx][0]) continue;
        
        isChecked[idx] = true;
        
        // depth를 1 증가 하고, 현재 피로도를 현재 던전의 소모 피로도을 차감 후 재귀 함수 호출
        DFS(depth + 1, remain - dungeons[idx][1], dungeons);
        
        isChecked[idx] = false;
    }
}


int solution(int k, vector<vector<int>> dungeons) {

    DFS(0, k, dungeons);
    
    return answer;
}