프로그래머스 LV2 - 피로도

문제 링크

내 풀이

# 최소 필요도보다 크면 소모하고 돌리고
# k > 최소 필요도 이면 result +1
# 위 조건 만족안하면 for문 종료하고 max_result값과 비교 후 다음 방법으로 시도
# 돌 때마다 max_result 최신화
# 모든 방법으로 다 돌면 result 출력 => how?
#
from itertools import *

def solution(k, dungeons):
    def can_explore(k, min_hp):
        if k >= min_hp:
            return True
    def explore(k, dungeons, max_result):
        hp_list = list(permutations(dungeons, len(dungeons)))
        for hp in hp_list:
            now = k
            result = 0
            for min_hp, use_hp in hp:
                if can_explore(now,min_hp):
                    now -= use_hp
                    result += 1
                    max_result = max(max_result, result)
                else:
                    max_result = max(max_result, result)
                    break
                    
        return max_result
    answer = explore(k,dungeons, 0)
    return answer 

다른 풀이

# 백트래킹을 위한 DFS
def dfs(cur_k, cnt, dungeons, visited):
  answer_max = cnt
  for i in range(len(dungeons)):
    # ➊ 현재 피로도(cur_k)가 i번째 던전의 최소 필요 피로도보다 크거나 같고,
    # i번째 던전을 방문한 적이 없다면
    if cur_k >= dungeons[i][0] and visited[i] == 0:
      visited[i] = 1  # i번째 던전을 방문 처리
      # ➋ 현재까지의 최대 탐험 가능 던전 수와
      # i번째 던전에서 이동할 수 있는 최대 탐험 가능 던전 수 중 큰 값을 선택하여 업데이트
      answer_max = max(
        answer_max, dfs(cur_k - dungeons[i][1], cnt + 1, dungeons, visited)
      )
      visited[i] = 0
  return answer_max

# 최대 탐험 가능 던전 수를 계산하는 함수
def solution(k, dungeons):
  visited = [0] * len(dungeons)  # ➌ 던전 방문 여부를 저장할 지역 배열
  answer_max = dfs(k, 0, dungeons, visited)  # ➍ DFS 함수 호출
  return answer_max

print(solution(80, [[80,20],[50,40],[30,10]]))

풀이 해석

• i = 0 에서 시작, 첫번째 dfs 호출
• dfs(cur_k - dungeons[0][1], cnt + 1, dungeons, visited) => dfs(60, 1, dungeons, visited)
• dfs(60, 1, dungeons, visited) 실행
• i = 0 일 땐 이미 방문, i = 1 일때 미방문이므로 if문 진입
• 두번째 dfs 호출
• dfs(cur_k - dungeons[1][1], cnt + 1, dungeons, visited) => dfs(20, 2, dungeons, visited)
• dfs(20, 2, dungeons, visited) 실행
• i = 0 이미 방문 i = 1 이미 방문 i = 2는 최소필요도를 만족못하므로 여기서 더이상 안들어가고 answer_max = 2로 마무리
• answer_max =2 를 하고 다음 코드에서 visited[1] = 0 으로 초기화하며 return answer_max
• 여기까지가 i = 1 로 들어갔을 때 결과이고
• dfs(60, 1, dungeons, visited) 실행에서 i = 2 로 진입 시 dfs(50, 2, dungeons, visited) 호출
• 이 때 visited[1] = 0으로 이전에 초기화를 해주었으므로 for문에서 i = 0은 이미 방문, i = 1일 때 미방문+ 조건 성립이므로
• dfs(0, 3, dungeons, visited) 호출
• i = 0, 1, 2에서 모두 방문하였으므로 answer_max값 3으로 갱신후 visited[1] = 0 으로 초기화 하면서 return answer_max
• dfs(50, 2, dungeons, visited) 리턴 전에 visited[2] = 0 으로 초기화 하며 answer_max 리턴
• dfs(60, 1 ,dungeons, visited ) 리턴 전에 visited[0] = 0으로 초기화 하며 answer_max 리턴
• 위 과정을 거쳐서
• dfs(k, 0, dungeons, visited) 처음 실행했을 때 for문에서의 i = 0일 때 상황 종결
• 위와 같은 방식으로 i = 1, 2 진행

배울 점

• dfs의 활용