[Programmers/C++] 광물 캐기

시간 복잡도

• 모든 곡괭이에 대한 DFS를 진행하면 $O(3^k)$의 시간이 걸립니다.
• k는 최대 15이므로 시간은 충분합니다.

문제 접근법

• 백트래킹을 이용하여 문제를 해결할 수 있습니다.
• 모든 곡괭이에 대해 DFS를 진행하며 피로도의 최솟값을 갱신합니다.
• 곡괭이가 존재한다면 광물을 5개 연속으로 캐며 DFS를 진행합니다.
• 완전탐색 혹은 그리디로 해결하려 했으나 복잡해서 검색으로 백트래킹으로 해결했습니다.

코드

#include <string>
#include <vector>
#include <climits>
#include <map>

using namespace std;

static map<string, int> pickIdx;
static int fatigue[3][3] = {{1,1,1}, {5,1,1}, {25,5,1}};

void DFS(vector<int>& picks, vector<string>& minerals, int& answer, int sum, int now)
{
    if(now==minerals.size() || (picks[0]==0 && picks[1]==0 && picks[2]==0))
    {
        answer=min(answer, sum);
        return;
    }
    
    for(int i=0; i<3; i++)
    {
        if(picks[i]!=0)
        {
            picks[i]--;
            
            int nextIdx=now;
            int tmpSum=sum;
            for(; nextIdx<now+5 && nextIdx<minerals.size(); nextIdx++)
                tmpSum+=fatigue[i][pickIdx[minerals[nextIdx]]];
            
            DFS(picks, minerals, answer, tmpSum, nextIdx);
            
            picks[i]++;
        }
    }

}

int solution(vector<int> picks, vector<string> minerals) {
    int answer = INT_MAX;
    
    pickIdx.insert({"diamond", 0});
    pickIdx.insert({"iron", 1});
    pickIdx.insert({"stone", 2});
    
    DFS(picks, minerals, answer, 0, 0);
    
    return answer;
}