[프로그래머스] 광물캐기 / Greedy , DFS(백트래킹)

 

Level. 2

 

 

문제

 

마인은 곡괭이로 광산에서 광석을 캐려고 합니다.

마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다.

각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다.

 

예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철과 돌을 캘때는 피로도가 1씩 소모됩니다.

각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.

마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다.

• 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
• 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
• 광물은 주어진 순서대로만 캘 수 있습니다.
• 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다.

즉, 곡괭이를 하나 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 과정을 반복하며, 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복하면 됩니다.

마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks와

광물들의 순서를 나타내는 문자열 배열 minerals가 매개변수로 주어질 때,

마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return 하는 solution 함수를 완성해주세요.

 

* 제한사항

• picks는 [dia, iron, stone]과 같은 구조로 이루어져 있습니다.
• 5 ≤ minerals의 길이 ≤ 50

 

 

풀이 1 - Greedy

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

// 1. Greedy

// 0) 곡괭이종류와 최대 피로도를 저장할 수 있는 구조체 Mine을 만든다. 
struct Mine
{
    int dia = 0;
    int irn = 0;
    int stn = 0;
    int max = 0; // 최대피로도
};

bool cmp(Mine a, Mine b){
    return a.max > b.max;
}

int solution(vector<int> picks, vector<string> minerals) {
    int energy[3][3] = {{1,1,1},{5,1,1},{25,5,1}};
    int maxMine = 0; // 가지고 있는 곡괭이로 캘 수 있는 광물의 최대 수
    int now = 0, answer = 0;
    vector<Mine> mines;
    map<string, int> m;
    m.insert({"diamond", 0});
    m.insert({"iron", 1});
    m.insert({"stone", 2});
    
    // 1) 가지고 있는 곡괭이로 캘 수 있는 광물의 최대 갯수를 구한다. 
    for(int i=0; i<picks.size(); i++){
        maxMine += picks[i]*5;    
    }   
    
    // 2) 곡괭이 하나로 다섯광물을 연속해서 캐야 하므로, 5개씩 각각의 곡괭이로 얻을 수 있는 피로도와 최대 피로도를 저장한다. 
    for(int i=0; i<minerals.size(); i+=5){
        Mine mm;
        for(int j=0; j<5; j++){
            // 3) 더이상 캘 수 있는 광물이 없거나, 최대 캘수있는 광물의 숫자가 넘었을 경우 반복문을 종료한다. 
            if((i+j) == minerals.size() || (i+j) == maxMine) break;
            mm.dia += energy[0][m[minerals[i+j]]];
            mm.irn += energy[1][m[minerals[i+j]]];
            mm.stn += energy[2][m[minerals[i+j]]];
            mm.max += energy[2][m[minerals[i+j]]];
        }
        mines.push_back(mm);
    }
    
    // 4) 최대 피로도를 기준으로 내림차순 정렬한다. 
    sort(mines.begin(), mines.end(), cmp);
    
    // 5) 최대 피로도에서 최저 피로도를 낼 수 있는 곡괭이 순 (다이아 -> 철 -> 돌) 으로 곡괭이를 소모시킨다. 
    for(int i=0; i<mines.size(); i++){
        if(picks[0] > 0){
            answer += mines[i].dia;
            picks[0] -= 1;
        }
        else if (picks[1] > 0){
            answer += mines[i].irn;
            picks[1] -= 1;
        }
        else if (picks[2] > 0){
            answer += mines[i].stn;
            picks[2] -= 1;
        }
        else break;
    }
    
    return answer;
}

 

해결방법

• 0) 곡괭이 종류와 최대 피로도를 저장할 수 있는 구조체 Mine을 만든다.
• 1) 가지고 있는 고괭이로 캘 수 있는 광물의 최대 개수를 maxMine에 저장한다. 
• 2) 곡괭이 하나로 다섯 개의 광물을 연속해서 캐야 하므로, 광물 5개씩 각각의 곡괭이로 얻을 수 있는 피로도와 최대 피로도를 mines에 저장한다. 
• 3) 더 이상 캘 수 있는 광물이 없거나, 최대로 캘 수 있는 광물의 숫자가 넘었을 경우 반복문을 종료한다. 
• 4) 최대 피로도를 기준으로 mines를 정렬한다. 
• 5) 최대 피로도에서 최저 피로도를 낼 수 있는 곡괭이순(다이아 -> 철 -> 돌)으로 곡괭이를 소모시킨다. 

 

 

 

풀이 2. - DFS 백트래킹

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <map>

using namespace std;

// 2. DFS 백트래킹

int energy[3][3] = {{1,1,1},{5,1,1},{25,5,1}};
map<string, int> m;
int mine_size;
int answer;

void dfs(vector<int> &picks, vector<string> &minerals, int now, int sum){
    
    int sumarr[3] = {0, }; 
    
    // 백트래킹. 현재까지 구한 피로도가 answer보다 크다면 더이상 탐색하는 의미가 없다. 
    if(sum > answer) return;
    
    // 종료조건
    if(now >= mine_size || (picks[0] == 0 && picks[1] == 0 && picks[2] == 0)){
        answer = min(answer, sum); 
        return;
    }
    
    int nnow = now;
    
    for(int i=0; i<5; i++){
        nnow = now + i;
        if(nnow >= mine_size){
            break;
        }
        sumarr[0] += energy[0][m[minerals[nnow]]];
        sumarr[1] += energy[1][m[minerals[nnow]]];
        sumarr[2] += energy[2][m[minerals[nnow]]];
        
    }
    
    for(int i=0; i<3; i++){
        if(picks[i] != 0){
            picks[i] -= 1;
            dfs(picks, minerals, nnow+1, sum + sumarr[i]);
            picks[i] += 1;
        }
    }
    
}

int solution(vector<int> picks, vector<string> minerals) {
    m.insert({"diamond", 0});
    m.insert({"iron", 1});
    m.insert({"stone", 2});
    mine_size = minerals.size();
    answer = mine_size * 25;
    
    dfs(picks, minerals, 0, 0);

    return answer;
}

 

 

백트래킹

해를 찾는 도중 지금의 경로가 해가 될 것 같지 않으면 더 이상 탐색을 멈추고 이전 단계로 되돌아가 해를 찾아 나가는 기법

• DFS : 가능한 모든 후보를 탐색하기 때문에 경우의 수를 최적으로 줄일 수 없다. 
• 백트래킹 : 모든 후보 중에서 특정 조건을 만족하는 경우만 탐색한다. DFS에서 조건문을 걸어 탐색을 중지시킨 뒤 이전단계로 돌아가서 다른 길을 탐색하도록 구현할 수 있다. 

 

 

 

 

 

 

 

---

https://school.programmers.co.kr/learn/courses/30/lessons/172927?language=cpp#

프로그래머스

https://velog.io/@leobit/DFS-BFS-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9Backtracking

DFS, BFS, 백트래킹(Backtracking)