본문으로 건너뛰기

작성일 : 2024.11.03

피로도 던전 문제

문제 설명​

게임 내 피로도 시스템을 활용한 던전 탐험 문제입니다. 각 던전은 두 가지 피로도 수치를 가지고 있습니다:

  • "최소 필요 피로도": 던전 입장을 위해 필요한 최소한의 피로도
  • "소모 피로도": 던전 완료 후 소모되는 피로도

유저의 현재 피로도가 주어졌을 때, 최대한 많은 던전을 탐험하려면 어떤 순서로 던전을 돌아야 하는지 구해야 합니다.

예시​

피로도가 80일 때 아래와 같은 던전이 있다면:

  • 던전 1: [최소 필요 피로도: 80, 소모 피로도: 20]
  • 던전 2: [최소 필요 피로도: 50, 소모 피로도: 40]
  • 던전 3: [최소 필요 피로도: 30, 소모 피로도: 10]

제한 조건​

  1. k (초기 피로도)

    • 범위: 1 ≤ k ≤ 5,000
    • 자연수

  2. dungeons 배열

    • 던전 개수: 1 ≤ 던전 수 ≤ 8
    • 각 던전 정보: [최소 필요 피로도, 소모 피로도]
    • 최소 필요 피로도 ≥ 소모 피로도
    • 1 ≤ 피로도 ≤ 1,000

해결 코드​

function solution(k, dungeons) {
  var answer = -1;
  let visited = new Array(dungeons.length).fill(false);
  let countArr = [];

  const dfs = (count, tired, visited) => {
    if (visited.indexOf(false) == -1 || tired <= 0) {
      countArr.push(count);
      return;
    }
    let over = true;
    for (let i = 0; i < dungeons.length; i++) {
      if (!visited[i] && tired >= dungeons[i][0]) {
        visited[i] = true;
        dfs(count + 1, tired - dungeons[i][1], visited);
        visited[i] = false;
        over = false;
      }
    }
    if (over) {
      countArr.push(count);
      return;
    }
  };
  dfs(0, k, visited);
  answer = Math.max(...countArr);
  return answer;
}

알고리즘 설명​

DFS(깊이 우선 탐색)와 백트래킹을 활용하여 모든 가능한 던전 순서를 탐색합니다:

  1. DFS 함수 매개변수

    • count: 현재까지 탐험한 던전 수
    • tired: 현재 남은 피로도
    • visited: 던전 방문 여부 배열

  2. 종료 조건

    • 모든 던전을 방문했을 때
    • 피로도가 0 이하가 됐을 때
    • 더 이상 탐험할 수 있는 던전이 없을 때

  3. 백트래킹

    • 현재 피로도로 탐험 가능한 던전을 찾아 방문
    • 방문 후 다시 미방문 상태로 복구하여 다른 경로 탐색

핵심 문법 요소​

  1. 방문 배열 초기화
let visited = new Array(dungeons.length).fill(false);
  1. Array.indexOf() 사용
visited.indexOf(false) == -1;
  1. 스프레드 연산자를 활용한 최대값 계산
Math.max(...countArr);
  1. 백트래킹을 위한 방문 처리/복구
visited[i] = true;
dfs(count + 1, tired - dungeons[i][1], visited);
visited[i] = false;

시간 복잡도​

  • O(n!): 던전을 방문하는 모든 순서를 탐색
  • n은 던전의 개수

공간 복잡도​

  • O(n): visited 배열과 재귀 호출 스택 사용
  • n은 던전의 개수