[프로그래머스] 광물캐기 (파이썬)

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/172927

문제해결

• 백트래킹 알고리즘으로 dfs 를 활용해서 풀어야한다.
• 재귀함수 종료조건으로 광물을 다 캐서 더이상 광물이 없거나, 곡괭이를 다 사용했을 경우 종료한다.

소스코드

weapons = {
        0 : 'diamond', 1: 'iron', 2: 'stone'
    }

def backtracking(w, picks, minerals, p, start):# 무기 종류, picks, mineral, 피로도, 슬라이싱에 필요한 인덱스번호
    ans = []
    if start >= len(minerals): #광물을 다캤을 경우
        return p
        
    arr = minerals[start:start+5]
    if w == 'diamond':
        for i in arr:
            p += 1
    elif w == 'iron':
        for i in arr:
            if i == 'diamond':
                p += 5
            else :
                p += 1
    else:
        for i in arr:
            if i == 'diamond':
                p += 25
            elif i == 'iron':
                p += 5
            else:
                p += 1
    if sum(picks) == 0: #곡괭이를 다 소진 했을 경우
        return p
    
    for i in range(3):
        if picks[i] > 0:
            picks[i] -= 1
            ans.append(backtracking(weapons[i], picks, minerals, p, start+5))
            picks[i] += 1
    
    return min(ans)
    
def solution(picks, minerals):
    ans = []
    p = 0
    start = 0
    for i in range(3):
        if picks[i] > 0:
            picks[i] -= 1
            ans.append(backtracking(weapons[i], picks, minerals,p, start))
            picks[i] += 1
    return min(ans)