광물 캐기(프로그래머스-연습문제)

문제

코드

class Solution {
    int answer = Integer.MAX_VALUE;
    public int solution(int[] picks, String[] minerals) {
        if(picks[0]!=0){
            int[] pick=picks.clone();
            pick[0]--;
            dfs(0,0,"diamond",pick,minerals);
        }
        if(picks[1]!=0){
            int[] pick=picks.clone();
            pick[1]--;
            dfs(0,0,"iron",pick,minerals);
        }
        if(picks[2]!=0){
            int[] pick=picks.clone();
            pick[2]--;
            dfs(0,0,"stone",pick,minerals);
        }
        return answer;
    }
    public void dfs(int sum, int index,String mineral,int[] picks,String[] minerals){
        for(int i=index;i<index+5;i++){
            if(i==minerals.length){
                answer=Math.min(answer,sum);
                return;
            }
            if(mineral.equals("diamond")) sum+=1;
            else if(mineral.equals("iron")){
                if(minerals[i].equals("diamond")) sum+=5;
                else sum+=1;
            }
            else{
                if(minerals[i].equals("diamond")) sum+=25;
                else if(minerals[i].equals("iron")) sum+=5;
                else sum+=1;
            }
        }
        boolean hasNext=false;
        if(picks[0]>0){
            int[] pick=picks.clone();
            pick[0]--;
            hasNext=true;
            dfs(sum,index+5,"diamond",pick,minerals);
        }
        if(picks[1]>0){
            int[] pick=picks.clone();
            pick[1]--;
            hasNext=true;
            dfs(sum,index+5,"iron",pick,minerals);
        }
        if(picks[2]>0){
            int[] pick=picks.clone();
            pick[2]--;
            hasNext=true;
            dfs(sum,index+5,"stone",pick,minerals);
        }
        if(!hasNext) answer=Math.min(answer,sum);
    }
}

풀이

dfs 알고리즘을 통해 다음 선택할 곡괭이 종류 3가지를 모두 선택해주면서 탐색하는 풀이를 사용하였다.

(1) 제일 처음 탐색할 곡괭이를 선택해서 dfs탐색을 시작해야 한다. 다이아,철,돌 곡괭이가 각각 0개가 아니면 시작 곡괭이로 하여 dfs 탐색을 보내준다. dfs 함수의 매개변수는 순서대로 (현재 피로도, 탐색중인 광물 위치, 현재 사용할 곡괭이, 남은 곡갱이 현황, 광물 순서) 이다.

(2) 현재 탐색할 광물 위치로부터 5개의 광물에 드는 피로도를 계산하여 더해준다. 만약 광물을 끝까지 캤으면, answer을 갱신하고 탐색을 종료한다.

(3) 다음 사용할 곡괭이를 골라 dfs() 함수를 재귀호출 한다. 다이아, 철, 돌 곡괭이의 수가 0보다 많으면 각각 탐색을 보낸다. 만약, 남은 곡괭이가 하나도 없다면 answer을 갱신하고, 탐색을 종료한다.

결과

처음에는 탐욕법 문제인줄 알고, 어떻게 곡괭이를 골라야 할 까 고민하고 있었다.
근데 제한사항 보니 모든 경우의 수를 탐색해도 시간 초과가 날 것 같지 않아 dfs 알고리즘으로 해결하였다. 코드가 살짝 긴 것 같지만 나름대로 만족스러운 풀이이다.
출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges