[프로그래머스 - Python3] 피로도

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

 제한사

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

입출력 예

k	dungeons	result
80	[[80, 20], [50, 40], [30, 10]]	3

 입출력 예 설명

현재 피로도는 80입니다.

만약, 첫 번째 → 두 번째 → 세 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 20입니다.
• 남은 피로도는 20이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30입니다. 따라서 세 번째 던전은 탐험할 수 없습니다.

만약, 첫 번째 → 세 번째 → 두 번째 던전 순서로 탐험한다면

• 현재 피로도는 80이며, 첫 번째 던전을 돌기위해 필요한 "최소 필요 피로도" 또한 80이므로, 첫 번째 던전을 탐험할 수 있습니다. 첫 번째 던전의 "소모 피로도"는 20이므로, 던전을 탐험한 후 남은 피로도는 60입니다.
• 남은 피로도는 60이며, 세 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 30이므로, 세 번째 던전을 탐험할 수 있습니다. 세 번째 던전의 "소모 피로도"는 10이므로, 던전을 탐험한 후 남은 피로도는 50입니다.
• 남은 피로도는 50이며, 두 번째 던전을 돌기위해 필요한 "최소 필요 피로도"는 50이므로, 두 번째 던전을 탐험할 수 있습니다. 두 번째 던전의 "소모 피로도"는 40이므로, 던전을 탐험한 후 남은 피로도는 10입니다.

따라서 이 경우 세 던전을 모두 탐험할 수 있으며, 유저가 탐험할 수 있는 최대 던전 수는 3입니다.

 

 

Solution

파이썬의 permutation 라이브러리를 사용하여 순열을 만들고, 만들어진 순열을 모두 탐색하면 된다.

그러나 공부하는 단계이기 때문에 BFS를 사용해서 해결했다. (BFS 처음 해봐서 많이 다른 블로그 많이 참고함)

 

트리 구조를 떠올리면 쉽다. 각 노드를 하나씩 탐색해가면서 조건에 맞는 값을 산출해내는 것.

인덱스 번호를 노드로 사용한다. 방문한 노드는 boolean값을 가지고 있는 list를 만들어서 방문할때마다 인덱스값을 True로 바꿔준다.

 

1. 루트(시작) 노드를 하나 정한다.
2. 만약 [30, 10] 노드로 갔다면, 자식 노드인 [50, 40] 노드를 큐에 넣고 다시 반복한다.
3. 위 과정에서 노드에 방문할 때마다 count는 1씩 올라간다.
4. 모든 노드를 시작 노드로 한 번씩 설정하여 돌린 다음, 가장 count가 높은 값을 리턴

코드

from collections import deque

def adventure(start, k, dungeons):
    queue = deque()
    queue.append([start, k, 0, [False for _ in range(len(dungeons))]])
    cnts = []
    
    while queue:
        location, energy, count, visited = queue.popleft()
        # 이미 탐험한 던전은 True로 방문처리
        visited[location] = True
        # 던전 탐험 후 남은 에너지 연산
        energy -= dungeons[location][1]
        # 던전 탐험 횟수 카운트
        count += 1
        # 탐험 횟수 저장
        cnts.append(count)

        # 남은 던전 중 아직 탐험하지 않은 던전이면서, 현재 피로도보다 최소 피로도가 낮은 던전 큐(탐험 대기 목록)에 추가
        for i in range(len(dungeons)):
            if visited[i] == False and energy >= dungeons[i][0]:
                # visited를 그대로 넘기면 레퍼런스를 넘겨주게 된다. 
                # 즉, 넘겨받은 변수의 요소를 변경하면 원본 visited의 요소도 변경된다는 것.
                
                # 따라서 visited[:]로 새로운 리스트를 생성하여 자식 노드를 새롭게 탐색한다.
                queue.append([i, energy, count, visited[:]])
    return max(cnts)
            

def solution(k, dungeons):
    answer = -1
    # 첫 던전부터 마지막 던전까지 차례대로 시작점으로 잡고 돌아보기
    for i in range(len(dungeons)):
        if dungeons[i][0] <= k:
            answer = max(answer, adventure(i, k, dungeons))
    return answer