[프로그래머스] BFS(or 완전탐색), 피로도

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

프로그래머스

 

문제 개요

input
k: 현재 피로도 (1이상 5000이하 자연수)
2차원 배열 dungeons: [["최소 필요 피로도", "소모 피로도"], [],...]
*"최소 필요 피로도" >=  "소모 피로도"
*각 값은 1이상 1000이하 자연수
*dungeons 내 원소 중복 가능.
ex) [[80,20],[50,40],[30,10]]

output
유저가 탐험할 수 있는 최대 던전 수
*k값이 0이상일 때까지 반복.

배열의 문제.
어떻게 배열해야 최대한 많은 개수의 던전을 탐험할 수 있을까.

 

 

구현 아이디어

BFS (queue 활용)

https://lets-hci-la-ai-withme.tistory.com/51

[알고리즘] BFS, 너비 우선 탐색

 

• 시작정점을 default((k, []))로 고정하고
  BFS 기반으로 - for문 통해 그다음 노드를 선택(단, 조건 충족하는 것만 queue에 인큐)
  
  
• graph는 주어진 2차원 배열 dungeons 사용
• node(첫 시작)을 (k, [])로 지정함.
  • k: (현재 업데이트된) k값
  • [] : visited 역할을 하는 'route'. 어떤 노드를 거쳤는지 노드 인덱스 남기는 리스트. default는 빈 리스트.
• queue 생성 필수: queue = deque() 
• while queue
• 중심 축(매번 업데이트되는 시작 정점)은 queue에서 popleft한 것. (k, route)
  • 그 안에서 for문으로 처리
    • 그다음 탐색할 노드(두 가지 조건 충족 )를 queue에 저장하거나
    • 조건 충족 안 할 경우, max 활용하여 answer 업데이트

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

 

좋은 아이디어

복습복습복습!