피로도 - 프로그래머스, c++

 

 

- 문제 풀이

"완전 탐색"을 사용해 푸는 문제였다.

완전 탐색 중에서도 이 문제는 단순 Brute-Fore 방법이나 순열로 해결할 수 도 있고 BFS를 구현해 해결할 수 도 있는 문제였다.

나는 전자의 방법을 선택했다.

 

 

- 코드

처음에 내가 작성하여 제출한 코드는 다음과 같다.

하지만 결과는 논리 오류(?)와 같은 결과가 나왔다.

논리적인 오류를 해결해야 했다.

"signal: segmentation fault (core dumped)"

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

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    
    
    //0부터 dungeons.size()-1까지의 수로 만들 수 있는 모든 수 조합을 vector에 저장
    int n = 1;
    vector<int> num(dungeons.size());  
    for(int i=0; i<dungeons.size(); i++) {
        num.push_back(i);
        n *= (i+1);
    }
    
    vector<vector<int>> temp(n,vector <int>(dungeons.size(),0));  
    int n1 = 0;
    do{
        for(int i=0; i<num.size(); i++) {
            temp[n1].push_back(num[i]);
        }
        n1++;
    }
    while(next_permutation(num.begin(), num.end()));
    
    
    // num에 저장한 숫자대로 dungeons에 접근해 최대로 갈 수 있는 던전 수를 계산하기
    for(int i=0; i<temp.size(); i++) {
        int count = 0;
        int sum = k;
        
        for(int j=0; j<num.size(); j++) {
            if(sum<=dungeons[temp[i][j]][0]) {
                sum -= dungeons[temp[i][j]][1];
                count++;
            }
            else {
                break;
            }
        }
        
        if(answer<count)
            answer = count;
    }
    
    
    return answer;
}

 

 

이를 해결하기 위해서는 다음과 같은 것들을 수정했다.

나는 1차원 벡터를 만들어 문제를 해결하려고만 했는데 그냥 2차원 벡터 dungeons를 그대로 사용하는 방식이 더 간단했다.

1. 2차원 벡터 dungeons를 바로 사용하기 위해 인덱스 [0], 가장 앞에 있는 수를 기준으로 정렬을 먼저 해주었다.

2. do{} 부분에서 바로 dungeons 벡터의 값을 가져와 k값을 계산할 수 있다.

3. answer과 count값을 비교할 때는 max() 함수를 통해 더 간단하게 구현할 수 있다.

3. dungeons는 2차원 벡터임에도 next_permutation(dungeons.begin(), dungeons.end()) 를 하면 인덱스 [0]의 가장 앞에 있는 수를 기준으로 모든 조합의 순열을 만들어 준다.

굳이 내가 짠 코드처럼 1차원 벡터만 순열 함수에 넣을 수 있는 건 아니다.

최종 코드는 다음과 같다.

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

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    
    
    //2차원 벡터를 sort하면 [0]에 담긴 수의 오름차순으로 정렬됨
    sort(dungeons.begin(), dungeons.end());
    
    
    //모든 조합의 숫자대로 탐색하기
    do{
        // num에 저장한 숫자대로 dungeons에 접근해 최대로 갈 수 있는 던전 수를 계산하기
        int count = 0;
        int k_sum = k;
        for(const auto& dungeon: dungeons) {
            if(k_sum >= dungeon[0]){
                k_sum -= dungeon[1];
                count++;
            }
            else {
                break;
            }
        }
        answer = max(count, answer);
    }
    while(next_permutation(dungeons.begin(), dungeons.end()));
    

    return answer;
}

 

 

단순 탐색과 순열을 사용하는 방법말고 BFS를 구현해 해결하는 방법도 있다.

BFS만 구현하면 코드적으로 더 간단해 보이긴 한다. 

BFS를 통한 구현은 링크를 참고해 공부했다.

(https://imnotabear.tistory.com/569)

1. 최소 피로도를 [] 배열 만들기

2. 소모 피로도를 [] 배열 만들기

3. isvisited [] 배열을 만들어 던전 탐험 유무를 확인하기

4. dfs()를 수행하며 남은 피로도가 최소 피로도 이상이며, 탐험하지 않은 던전인 경우, 탐험하기

5. dfs() 실행하며 count한 값을 반환하기