[프로그래머스 2레벨] 광물 캐기 (C++)

#include <string>
#include <vector>

using namespace std;

int arr[3][3] = {{1, 1, 1}, {5, 1, 1}, {25, 5, 1}}; //다이아, 철, 돌

int getIndex(string minerals)
{
    if(minerals[0] == 'd') return 0;
    else if(minerals[0] == 'i') return 1;
    else return 2;
}

void dfs(vector<int>picks, vector<string>minerals, int idx, int total, int& answer)
{
    if(idx >= minerals.size() || (picks[0]==0 && picks[1]==0 && picks[2]==0)) //곡괭이 모두 사용 or 광물 모두 캠
    {
        answer = min(answer, total);
        return;
    }
    
    for(int i=0; i<3; i++) //곡괭이 3개 체크
    {
        if(picks[i] <=0) continue; //없는 곡괭이 스킵
        int tmp = 0;
        for(int j=idx; j<idx+5 && j<minerals.size(); j++) //5개 광물 채광
        {
            int m = getIndex(minerals[j]); //광물 인덱스
            tmp += arr[i][m]; //피로도 누적
        }
        
        picks[i]--; //곡괭이 사용
        dfs(picks, minerals, idx+5, total+tmp, answer);
        picks[i]++; //백트래킹
    }
}

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 50*25+1;
    
    dfs(picks, minerals, 0, 0, answer);
        
    return answer;
}

 

먼저 주어진 표 값에 따라 곡괭이 - 광물에 따른 3x3 피로도 배열을 생성해준다.

그리고 재귀를 통해서 각 곡괭이 사용 케이스를 모두 탐색할 것이며, 여기서 최소값을 저장해 출력하게 된다.

 

종료 조건은 곡괭이 모두 사용 또는 광물이 모두 채굴됐을 때이기에 해당 조건에 따라 최소값을 갱신한다.

곡괭이가 3개이기 때문에 첫 반복문은 3개까지 체크하고, 없는 곡괭이가 생길 수 있기에 해당 경우는 스킵한다.

한 번의 곡괭이가 5개의 광물을 연달아 캐야하기 때문에, 다음 반복문은 현재 인덱스 + 5까지 탐색한다.

이때 총 광물 개수를 초과하는 범위까지 탐색할 수도 있기 때문에 광물의 총량 또한 같이 체크해주어야 한다.

 

해당 5개의 광물을 탐색하면서, 각 광물에 대한 인덱스를 얻고, 앞서 선언한 3x3 배열에 따라 피로도를 누적하여 합산한다.

(i -> 곡괭이, j -> 광물)

 

지금 사용한 곡괭이는 개수를 감소시켜주고, 다시 재귀를 통해 다음 5개의 광물을 탐색한다.

다른 케이스에서 최소값이 발견 될 수 있으므로, 백트래킹으로 사용한 곡괭이는 다시 증가시켜준다.

이를 통해 모든 케이스를 탐색하며 최소값을 찾아 반환한다.