[프로그래머스] 광물 캐기(Java) - DFS

📌 핵심 요약

• 곡괭이 하나 = 연속된 광물 5개 — 광물을 하나씩 결정하는 것이 아니라, 5개 묶음 단위로 어떤 곡괭이를 쓸지 결정하는 문제다
• DFS + 백트래킹 — 각 묶음마다 다이아/철/돌 곡괭이 3가지 분기를 시도하고, 곡괭이를 되돌리며 전체 경우를 탐색했다
• 가지치기 — 현재 피로도 합이 이미 찾은 최솟값 이상이면 더 탐색하지 않고 종료한다

 

목차

1 문제 분석

Programmers #172927

광물 캐기

곡괭이 합 ≤ 9 · 광물 ≤ 50

난이도: Lv.2

다이아몬드, 철, 돌 곡괭이가 각각 주어지고, 광물 목록을 앞에서부터 순서대로 캔다. 곡괭이 하나는 광물 5개를 캐면 더 이상 사용할 수 없다. 곡괭이 종류와 광물 종류의 조합에 따라 피로도가 다르게 소모될 때, 최소 피로도를 구하는 문제다.

풀이 과정

1. 곡괭이 하나가 담당하는 범위는 항상 연속된 5개이므로, 결정 단위를 광물 1개가 아닌 5개 묶음으로 잡는다
2. 각 묶음마다 다이아 / 철 / 돌 곡괭이 3가지 분기를 DFS로 탐색한다
3. 광물이 소진되거나 곡괭이가 모두 소진되면 피로도 합으로 최솟값을 갱신한다
4. 현재 합이 이미 찾은 최솟값 이상이면 가지치기로 조기 종료한다

피로도 표는 다음과 같다. 좋은 곡괭이일수록 어떤 광물이든 싸게 캘 수 있고, 특히 다이아몬드를 돌 곡괭이로 캐면 25라는 큰 비용이 든다.

곡괭이 \ 광물	다이아몬드	철	돌
다이아 곡괭이	1	1	1
철 곡괭이	5	1	1
돌 곡괭이	25	5	1

2 접근 방식

결정 단위는 광물이 아니라 5개 묶음

광물은 반드시 앞에서부터 캐야 하고, 곡괭이 하나는 정확히 5개를 담당한다. 따라서 광물 하나하나를 어떻게 캘지 고민할 필요가 없고, "이번 5개 묶음에 어떤 곡괭이를 쓸 것인가"만 결정하면 된다. 이렇게 결정 단위를 재정의하면 탐색 트리의 깊이는 최대 묶음 수(≤ 10), 분기는 3이 되어 완전탐색이 충분히 가능해진다.

ℹ️

시간 복잡도

곡괭이 합이 최대 9개이므로 탐색 깊이도 최대 9다. 분기 3에 깊이 9면 3⁹ = 19,683가지 수준이라 가지치기 없이도 여유롭게 통과한다.

백트래킹과 가지치기

곡괭이 배열 picks를 그대로 재사용하기 위해, 분기 진입 전에 picks[i]--로 사용 처리하고 재귀에서 돌아온 뒤 picks[i]++로 복원했다. 또한 피로도는 음수가 될 수 없으므로, 진행 중인 합이 이미 찾은 최솟값 이상이면 그 경로는 더 볼 필요가 없다. sum >= answer일 때 즉시 리턴하는 가지치기를 넣었다.

3 전체 코드

 

Java — Solution.java

import java.util.*;

class Solution {
    int answer = Integer.MAX_VALUE;

    public int solution(int[] picks, String[] minerals) {
        dfs(picks, minerals, 0, 0);
        return answer;
    }

    public void dfs(int[] picks, String[] minerals, int sum, int index) {
        // 광물 소진 or 곡괭이 전부 소진 → 최솟값 갱신
        if (index >= minerals.length || (picks[0] == 0 && picks[1] == 0 && picks[2] == 0)) {
            answer = Math.min(answer, sum);
            return;
        }

        // 가지치기: 이미 최솟값 이상이면 탐색 중단
        if (sum >= answer) {
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (picks[i] > 0) {
                picks[i]--;

                // 이번 곡괭이로 캘 연속 5개 묶음의 피로도 계산
                int current_sum = 0;
                int current_idx = Math.min(index + 5, minerals.length);
                for (int j = index; j < current_idx; j++) {
                    current_sum += cal(minerals[j], i);
                }
                dfs(picks, minerals, sum + current_sum, current_idx);

                picks[i]++; // 백트래킹: 곡괭이 복원
            }
        }
    }

    public int cal(String mineral, int pick) {
        switch (pick) {
            case 0 : return 1; // 다이아몬드 곡괭이
            case 1 : if (mineral.equals("diamond")) return 5; // 철 곡괭이
                     return 1;
            case 2 : if (mineral.equals("diamond")) { // 돌 곡괭이
                         return 25;
                     } else if (mineral.equals("iron")) {
                         return 5;
                     } else {
                         return 1;
                     }
            default : return 0;
        }
    }
}

4 다른 접근: 그리디

이 문제는 그리디로도 풀 수 있다.

핵심 관찰은 곡괭이가 총 p개일 때 캐는 블록이 무조건 앞에서부터 min(p, 전체 블록 수)개로 고정된다는 점이다.

어떤 블록을 캘지는 선택의 여지가 없으므로, 남는 결정은 "어느 블록에 어느 곡괭이를 배정할 것인가"뿐이다.

따라서 캘 블록들을 다이아 수 내림차순 → 철 수 내림차순으로 정렬한 뒤, 좋은 곡괭이부터 순서대로 배정하면 된다.

정렬 기준을 총 피로도가 아닌 다이아 수로 잡는 이유는, 곡괭이를 업그레이드했을 때 절약되는 피로도가 다이아 개수에 압도적으로 좌우되기 때문이다.

다이아 1개짜리 블록과 철 5개짜리 블록은 돌 곡괭이 기준 피로도(25)가 같지만, 다이아 곡괭이를 줬을 때의 절약량은 각각 24와 20으로 다이아 쪽이 크다.

💡

탐색 문제가 배정 문제로 붕괴하는 순간

겉보기에는 탐색 문제지만, "캘 블록이 고정"이라는 구조를 증명하는 순간 단순 배정 문제로 바뀐다. DFS는 이 고정성을 몰라도 전 경우를 훑기 때문에 정답이 보장되고, 그리디는 구조를 먼저 파악해야 하는 대신 코드가 훨씬 단순해진다. 이번 문제는 제약이 작아 어느 쪽이든 통과한다.

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.