[프로그래머스] Level 2 - 피로도 (Python)

 

 

 

 

https://programmers.co.kr/learn/courses/30/lessons/87946

코딩테스트 연습 - 피로도

 

 

 

 

✅ Solution

완전 탐색과 그래프를 이용한 방법 두 가지가 있었다.

 

1. 완전 탐색

• permutations로 가능한 조합을 모두 구한 후, answer값을 비교하며 큰 값을 리턴한다.

2. BFS

• k와 빈 배열로 deque 배열을 만든다.
  • k는 남아있는 피로도, []은 방문한 던전을 의미한다.
• 던전의 길이만큼 반복문을 돌면서
  • 만약 k가 최소 필요 소모도보다 크고, 해당 던전을 방문한 적이 없다면 queue에 추가해준다.
  • 그렇지 않다면 answer와 len(route)와의 길이를 비교하여 큰 값을 구한 후 리턴한다.

 

 

 

 

✅ Code

## 완전 탐색
from itertools import permutations

def solution(k, dungeons):
    answer = -1
    candidates = list(permutations([x for x in range(len(dungeons))], len(dungeons)))

    for candidate in candidates:
        temp, cnt = k, 0
        for idx in candidate:
            if temp >= dungeons[idx][0]:
                temp -= dungeons[idx][1]
                cnt += 1
        answer = max(answer, cnt)

    return answer

## BFS
from collections import deque

def solution(k, dungeons):
    answer = -1
    queue = deque()
    queue.append((k, []))

    while queue:
        k, route = queue.popleft()
        for i in range(len(dungeons)):
            a, b = dungeons[i]
            if k >= a and i not in route:
                temp = route + [i]
                queue.append((k - b, temp))
            else:
                answer = max(answer, len(route))

    return answer