[Python] 프로그래머스 - 광물 캐기

프로그래머스 광물 캐기 문제는 주어진 곡괭이를 사용해 광물을 캐는 방법 중 피로도가 최소가 되는 경우를 구하는 문제다. 난이도는 레벨2이며 백트래킹, 그리디를 통해 해결할 수 있다.

 

프로그래머스 - 광물 캐기 문제 정보

알고리즘 분류

- 백트래킹, 그래프 탐색

- 그리디

난이도

- level 2

 

문제 요약

• 곡괭이 종류는 다이아, 철, 돌이 있으며 각각 0~5개 주어진다.
  • 곡괭이 1개 당 5개의 광물까지 캘 수 있다.
  • 곡괭이를 선택하면 그 곡괭이를 5번 사용하고 나서 다음 곡괭이를 사용할 수 있다.
• 광물을 캐는 피로도는 곡괭이 종류와 광물 종류에 따라 다르다. (TC와 관계없이 고정되어있음)
• 광물은 주어진 순서대로만 캘 수 있다.
• 모든 광물을 캐거나, 곡괭이를 모두 사용할 때까지 광물을 캔다.

 

문제 풀이 과정

• 곡괭이를 하나씩 소진하면서 피로도를 계산한다.
• 현재까지의 최솟값보다 피로도가 커지면 pruning한다.
• 각 곡괭이를 소진한 뒤의 상태를 큐에 저장한다.

코드

import collections

def solution(picks, minerals):
    answer = 25 * 50
    names = {"diamond": 0, "iron": 1, "stone": 2}
    fatigues = [[1,1,1], [5,1,1], [25,5,1]]
    
    queue = collections.deque()
    # (남은 곡괭이 수 array, 현재 곡괭이, 현재 곡괭이 잔여 횟수, 현재 광물, 현재까지 피로도)
    queue.append((picks,-1,0,0,0))
    
    while queue:
        rest_picks, cur_pick, cur_pick_rest, cur, cur_fatigue = queue.popleft()
        
        # 광물을 모두 캤거나, 곡괭이를 모두 사용했으면 answer와 비교하여 갱신
        if cur >= len(minerals) or (rest_picks == [0,0,0] and cur_pick_rest == 0):
            answer = min(answer, cur_fatigue)
            continue
        
        # 현재까지의 피로도가 answer보다 크거나 같으면 pass
        if cur_fatigue >= answer:
            continue
        
        mineral = names[minerals[cur]]
        
        # 현재 사용중인 곡괭이를 더 사용할 수 있는 경우
        if cur_pick_rest > 0:
            next_rest_picks = [rest for rest in rest_picks]
            queue.append((next_rest_picks, cur_pick, cur_pick_rest-1, cur+1, cur_fatigue + fatigues[cur_pick][mineral]))
        
        # 새로운 곡괭이를 선택해야 하는 경우, 각 곡괭이에 대한 경우를 큐에 넣음
        else:
            for pick, rest in enumerate(rest_picks):
                if rest == 0:
                    continue

                next_rest_picks = [rest for rest in rest_picks]
                next_rest_picks[pick] -= 1
                queue.append((next_rest_picks, pick, 4, cur+1, cur_fatigue + fatigues[pick][mineral]))
    
    return answer