[DFS] 프로그래머스 광물캐기 (실패분석 - 아이디어 부족)

접근

광물캐기

저는 처음에 저의 풀이가 맞다고 생각했습니다.
로직은 다음과 같습니다.

1. 광물의 순서도를 5개의 크기로 자르기
2. 그 순서도에 맞게 남아 있는 곡괭이로 진행했을 때
   가장 작은 피로도를 가진 곡괭이 제거하고 피로도에 더하기
3. 위 과정은 모든 곡괭이를 썼거나 순서도에 존재하는 광물을 모두 제거할 때까지 반복한다.
4. 5개의 크기로 자르고 남은 순서도의 경우 곡괭이가 남아있는 경우 다시 최소의 피로도를 구한다.

하지만 위 방법은 틀렸습니다.
왜냐하면 곡괭이를 선택하는 기준은 현재 남아있는 광물의 순서도에 따라 가장 작은 피로도를 구하는 것이 아니라 미래를 생각해서 선택해야 합니다.

picks = [1, 0, 1]
minerals = ["stone", "stone", "stone", "stone", "stone", "iron", "iron", "iron", "iron", "iron", "diamond", "diamond"]

의 경우 앞에 5개의 순서도를 자른다고 가정합시다.
그러면 ["stone", "stone", "stone", "stone", "stone"]입니다.
이 광물에 따라 남아 있는 곡괭이의 피로도는 각각 5입니다.
그럼 둘 중에 누굴 선택해야 할까요?

제 풀이의 경우는 다이아몬드 곡괭이를 선택합니다.
그럴 경우 최종 피로도를 30이 됩니다.

하지만 만약에 다이아몬드 곡괭이가 아닌 돌 곡괭이를 선택했다면
최종 피로도는 10 입니다.

즉 제 풀이는 미래를 생각하지 않고 계산하기 때문에 틀렸습니다.

따라서 저는 DFS를 이용하여 다시 풀었습니다.
로직은 아래와 같습니다.

1. DFS를 이용해서 곡괭이를 고르는 모든 경우의 수를 만든다.
   하지만 이전 DFS와 다르게 boolean을 통한 상태 배열의 백트랙킹이 아니라 곡괭이 수를 다시 되돌려 놓는 백트랙킹입니다. 사실 이 부분을 구현하는게 가장 재미있었습니다.

   static void dfs(int[] picks, int level, String gok){
          if(level==cnt){
              list.add(gok);
          }else{
              for(int i=0;i<3;i++){
                  if(picks[i]>0){
                      picks[i]--;
                      dfs(picks,level+1,gok+i);
                      picks[i]++;
                  }
              }
                 
          }
      }

2. 모든 경우의 수를 가지고 가장 작은 피로도를 구합니다.

따라서 저는 틀린 풀이와 DFS로 성공한 풀이 두 가지를 정리했습니다.

틀린 풀이

import java.util.*;

class Solution {
    // 다이아몬드, 철, 돌 순으로
    static int[] dia = {1,5,25};
    static int[] iron = {1,1,5};
    static int[] stone = {1,1,1};
    static int[] Picks;
    static int answer=0;
    
    
    
    public int solution(int[] picks, String[] minerals) {
        
        // 각 곡괭이는 종류에 상관엇이 광물 5개를 캔 후에는 사용할 수 없다
        // 최소의 피로도
        // 사용할 수 있는 곡괭이 중 아무거나 하나-> 광물 캐기
        // 한번 사용시작하면 사용할 수 없을 때까지
        // 광물은 주어진 순서대로만
        // 광산에 잇는 모든 광물 혹은 더 사용할 광물이 없을 때까지
        
        // 가지고 있는 곡괭이의 개수 picks [dia, iron, stone]//최소 1개 이상
        // 광물들의 순서 minerals // 문자열
        
        
        
        // 앞의 5개를 최소로 캘수 있는 곡괭이 구하기
        // 피로도 계산해서 가장 작은 피로도 곡괭이 pick 그 곡괭이가 없을 다음 곡괭이 pick
        
        
        Picks = picks;
        
        int next=0;
        
        for(int i=0;i+5<=minerals.length;){
            next = i+5;
            // 배열 자르기
            String[] arr = Arrays.copyOfRange(minerals, i, next);
            if(allZeroPick(Picks)) break; 
            pickGok(arr);   
            i=i+5;
        }
        
        
        // 마지막에 5개에서 남은 아이들
        if(minerals.length % 5 != 0){
            if(!allZeroPick(Picks)){
             String[] arr = Arrays.copyOfRange(minerals,next,minerals.length);
             pickGok(arr); 
            }  
        }
        
        
            
            
        return answer;
    }
    
    static void pickGok (String[] arr){
        
        //0번째는 다이어모든, 1번째는 철, 3번째가 돌 곡괭이에 해당
        int[] gok = new int[3]; 
        
        // 남아있는 곡괭이들로 arr에 있는 광물을 캣을 때의 피로도 구하기
        for(int i=0;i<3;i++){
            if(Picks[i]>0){ // 남아있는 곡괭이가 있으면
                for(int j=0;j<arr.length;j++){
                    if(arr[j].equals("diamond")){
                        gok[i]+=dia[i];
                    }else if(arr[j].equals("iron")){
                        gok[i]+=iron[i];
                    }else{
                         gok[i]+=stone[i];
                    }  
                }  
            }    
        }
        
        // 각 곡괭이의 피로도를 통해서 가장 작은 피로도를 가지는 곡괭이 고르고
        // 곡괭이 재고 -1
        int min = Integer.MAX_VALUE;
        int index =0;
        for(int i=0;i<3;i++){
            if(gok[i]!=0 && gok[i]<min){
                min=gok[i];
                index=i;
            }
        }
        
        answer+=min;
        System.out.println(answer);
        Picks[index]-=1;
        
    }
    
    static boolean allZeroPick(int[] picks){
        for(int i=0;i<3;i++){
            if(picks[i]>0)
                return false;
        }
        return true;
        
    }
}

DFS를 이용한 풀이 (성공)

import java.util.*;

class Solution {
    // 다이아몬드, 철, 돌 순으로
    static int[] dia = {1,5,25};
    static int[] iron = {1,1,5};
    static int[] stone = {1,1,1};
    
    static int[] Picks;
    static int cnt;
    
    
    static ArrayList<String> list = new ArrayList<>();
    public int solution(int[] picks, String[] minerals) {
        
        int answer=0;
        
        //곡괭이 종류를 모든 경우의 수로 만들기
        // 그 경우의 수에서 가장 작은 피로도를 갖는 경우를 return하기
        
        
        cnt = 0;
        for(int p : picks){
            cnt+=p;
        }
        
        
        // 모든 경우의 수 만들기
        dfs(picks,0,"");
        
        int min = Integer.MAX_VALUE;
        
        for(String l: list){
            int piro=0;
            int index=0;
            // 이번 경우의 수의 길이
            for(int i=0;i<l.length();i++){
              // 광물 캐기
              for(;index<minerals.length;){
                  if(minerals[index].equals("diamond")){
                      piro+=dia[l.charAt(i)-'0'];
                  }else if(minerals[index].equals("iron")){
                      piro+=iron[l.charAt(i)-'0'];
                  }else{
                       piro+=stone[l.charAt(i)-'0'];
                  }
                  index++;
                  if(index%5==0) break;  
              }
                
     
            }
            //System.out.println(piro);
            if(piro<min) min=piro;
            
            
        }
        
        return min;
        
    
    }
    
    static void dfs(int[] picks, int level, String gok){
        if(level==cnt){
            list.add(gok);
        }else{
            for(int i=0;i<3;i++){
                if(picks[i]>0){
                    picks[i]--;
                    dfs(picks,level+1,gok+i);
                    picks[i]++;
                }
            }
               
        }
    }
}