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

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

프로그래머스

 

코드

---

def solution(picks, minerals):
    
    graph =[[1,1,1],
            [5,1,1],
            [25,5,1]] 
    
    def mineralNum(s):
        if s == "diamond":
            return 0
        if s == "iron":
            return 1
        if s == "stone":
            return 2
        
    def DFS(cnt,prePick,total):
        nonlocal answer,picks
        
        if cnt >= len(minerals):
            answer = min(answer,total)
            return
        
        mNum = mineralNum(minerals[cnt])
        
        if (cnt+1) % 5 == 0:
            if picks.count(0) == 3:
                answer = min(answer,total+graph[prePick][mNum])
                return
            for pick in range(len(picks)):
                if picks[pick] > 0:
                    picks[pick] -= 1
                    DFS(cnt+1, pick, total+graph[prePick][mNum])
                    picks[pick] += 1
            return
        else:
            DFS(cnt+1, prePick, total+graph[prePick][mNum])
            
    answer = 1e9
    for pick in range(len(picks)):
        if picks[pick] > 0:
            picks[pick] -= 1
            DFS(0,pick,0)
            picks[pick] += 1
    
    return answer

 

풀이

---

문제내용이 마인크래프트에서 영감을 받은 문제인 것 같아서 재밌었던 문제이다.

 

한 곡괭이당 무조건 5개씩 캘 수 있으니 5개를 캘 때마다 곡괭이를 바꿔주어야 한다.

처음에는 이 곡괭이를 바꿔줄 때 효율성을 계산해서 다음 5개를 가장 적은 시간에 해결할 수 있는 곡괭이를 선택할까 했다.

하지만 이 효율성을 계산하는 과정이 너무 복잡하고 따져야 할 조건이 많았다. 그래서 이 문제는 무조건 완전탐색이라고 생각했다.

 

5번째 광물, 즉 곡괭이를 바꿔줘야 할 타이밍이 올 때마다 DFS로 가지를 뻗어나간다.

각각의 가지들은 하나의 곡괭이를 선택하여 3방향씩 뻗어나가므로 시간복잡도는 3^10이 최대가 되어서 시간초과가 나지는 않을 것이라 생각했다.

모든 광물을 캐거나 곡괭이가 모두 사용되면 정답을 갱신하고 그렇지 않다면 계속해서 가지를 뻗어나간다.

가지를 뻗어나갈 때 picks[pick] -= 1 은 사용한 곡괭이의 개수를 줄이는 과정인데 DFS를 수행한 이후에는 다른 가지에 영향이 가지 않도록 다시 되돌려주어야 한다는 것을 잊으면 안된다.