[JavaScript] 피로도 - 완전탐색

프로그래머스 - 알고리즘 고득점 Kit 완전탐색 편

 

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다.

이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다.

"최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며,

"소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다.

 

예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다.

유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

 

 

 

function solution(k, dungeons) {
  let maxCount = 0;
  
  function explore(currentK, visited, count) {
    maxCount = Math.max(maxCount, count);
    
    for(let i = 0;i < dungeons.length;i++) {
      if (!visited[i] && currentK >= dungeons[i][0]) {
        visited[i] = true;
        explore(currentK - dungeons[i][1], visited, count+1);
        visited[i] = false;
      }
    }
  }
    
  explore(k, Array(dungeons.length).fill(false), 0);
  return maxCount;
}

 

 

 

1. 함수의 기본 구조

function solution(k, dungeons)

- k: 현재 피로도
- dungeons: 던전 정보를 담은 2차원 배열 (각 던전의 [최소 필요 피로도, 소모 피로도])

2. 전역 변수

let maxCount = 0;

- 최대로 탐험할 수 있는 던전 수를 저장하는 변수

3. 재귀 함수 explore

function explore(currentK, visited, count)

- currentK: 현재 남은 피로도
- visited: 각 던전의 방문 여부를 저장하는 배열
- count: 현재까지 탐험한 던전의 수

4. 재귀 함수의 동작 과정

maxCount = Math.max(maxCount, count);

- 현재까지 탐험한 던전 수와 최대값을 비교하여 갱신

5. 던전 탐험 로직

for(let i = 0;i < dungeons.length;i++) {
  if (!visited[i] && currentK >= dungeons[i][0]) {

- 모든 던전을 순회하면서:
  - 아직 방문하지 않은 던전이고
  - 현재 피로도가 던전의 최소 필요 피로도 이상인 경우 탐험 가능

6. 백트래킹 과정

visited[i] = true;
explore(currentK - dungeons[i][1], visited, count+1);
visited[i] = false;

- 던전을 방문 표시
- 피로도를 감소시키고 던전 수를 증가시켜 재귀 호출
- 탐색이 끝나면 방문 표시를 제거 (백트래킹)

7. 초기 호출

explore(k, Array(dungeons.length).fill(false), 0);

- 초기 피로도(k)
- 모든 던전을 방문하지 않은 상태의 배열
- 탐험한 던전 수 0으로 시작

8. 최종 결과 반환

return maxCount;

- 가능한 최대 던전 탐험 수를 반환