[프로그래머스] (JavaScript) 피로도 - DFS

[프로그래머스] (JavaScript) 피로도 - DFS

문제 설명

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이다.

---

정답 코드

function solution(k, dungeons) {
  let answer = 0;
  const visited = new Array(dungeons.length).fill(false)

  function DFS(k, count) {
    for (let i = 0; i < dungeons.length; i++) {

      if (!visited[i] && dungeons[i][0] <= k) {
        visited[i] = true;
        DFS(k - dungeons[i][1], count + 1);
        visited[i] = false;
      }
    }
    answer = Math.max(answer, count);
  }
  DFS(k, 0);
  return answer;
}

---

코드 풀이

const visited = new Array(dungeons.length).fill(false)

 

각 던전의 방문여부를 나타낼 배열을 생성한다.

 

function DFS(k, count) {
  for (let i = 0; i < dungeons.length; i++) {

//  if (!visited[i] && dungeons[i][0] <= k) {
//    visited[i] = true;
//    DFS(k - dungeons[i][1], count + 1);
//    visited[i] = false;
//  }
  }
  answer = Math.max(answer, count)
}

 

첫 번째 던전을 처음으로 방문하는 for 문이 시작한다.

 

if (!visited[i] && dungeons[i][0] <= k) {
//  visited[i] = true;
//  DFS(k - dungeons[i][1], count + 1);
//  visited[i] = false;
}

 

첫 번째 던전의 방문이 false 이고, 남은 피로도가 첫 번째 던전의 "최소 필요 피로도"보다 크거나 같은지 확인한다.

 

visited[i] = true;
DFS(k - dungeons[i][1], count + 1);

 

만약에 조건에 부합한다면, 해당 던전을 방문표시 하고 DFS(던전 방문 후 피로도, 던전 방문 횟수)를 계산하여 재귀함수를 호출한다.

 

이렇게 첫 번째 for 문이 열려있는 상태에서, 다시 첫 번째 던전부터 세 번째 던전까지 방문한다. 

첫 번째 for 문에서 첫 번째 던전을 방문표시 했으니, 조건에 부합하지 않아 두 번째 던전의 조건을 확인할 것이다.

 

function DFS(k, count) {
  for (let i = 0; i < dungeons.length; i++) {
//
//  if (!visited[i] && dungeons[i][0] <= k) {
//    visited[i] = true;
//    DFS(k - dungeons[i][1], count + 1);
//    visited[i] = false;
//  }
  }
  answer = Math.max(answer, count)
}

 

이렇게 첫 번째 for 문이 열려있는 상태에서 첫 번째부터 세 번째 던전까지 다 확인했다면, for 문이 종료된다.

첫 번째 던전을 처음으로 방문한 for 문이 종료되고, answer 값(초기값 0)과 던전 방문 횟수 중 큰 값으로 answer 을 갱신한다.

 

visited[i] = false;

 

그리고, 첫 번째 던전을 처음으로 방문한 것을 미방문처리 하고 두 번째 던전을 처음으로 방문하는 for 문이 시작한다.

---

풀이 상세

모든 경우를 구한 후, 최종적으로 가장 많이 들어가는 횟수를 구해야 하므로 DFS 방식으로 풀었다.

 

입출력 예시로 설명해보겠다.

 

k : 80

dungeons : [[80, 20] [50, 40] [30, 10]]

 

1번만 먼저 들어가는 경우만 보면,

 

DFS(80, 0)

i = 0 (f, f, f) → f && 80 <= 80 [조건 O]  → (t, f, f) DFS(60, 1)

      DFS(60, 1)

      ii = 0 (t, f, f) → t (방문됨) [조건 X]

      ii = 1 (t, f, f) → f && 50 <= 60 [조건 O] → (t, t, f) DFS(20, 2)

            DFS(20, 2)

            iii = 0 (t, t, f) → t (방문됨) [조건 X]

            iii = 1 (t, t, f) → t (방문됨) [조건 X]

            iii = 2 (t, t, f) → f && 30 <= 20 [조건 X]

            for 문 종료 → 1, 2 들어감 answer 0, 2 → answer = 2

      → (ii = 1) 미방문처리 (t, f, f)

      ii = 2 (t, f, f) → f && 30 <= 60 [조건 O] → (t, f, t) DFS(50, 2)

            DFS(50, 2)

            iv = 0 (t, f, t) → t (방문됨) [조건 X]

            iv = 1 (t, f, t) → f && 50 <= 50 [조건 O] → (t, t, t) DFS(10, 3)

                  DFS(10, 3)

                  v = 0 (t, t, t) → t (방문됨) [조건 X]

                  v = 1 (t, t, t) → t (방문됨) [조건 X]

                  v = 2 (t, t, t) → t (방문됨) [조건 X]

                  for 문 종료 → 1, 3, 2 들어감 answer 2, 3 → answer = 3

            → (iv = 1) 미방문처리 (t, f, t)

            iv = 2 (t, f, t) → t (방문됨) [조건 X]

            for 문 종료 → 1, 3 들어감 answer 3, 2 → answer = 3

     → (ii = 2) 미방문처리 (t, f, f)

     for 문 종료 → 1 들어감 answer 3, 1 → answer = 3

→ (i = 0) 미방문처리 (f, f, f)

i = 1 (f, f, f) ...

 

: 1먼저 방문한 for 문에서

1. 1 > 2 > 3
2. 1 > 3 > 2
3. 1 > 3
4. 1 > 2
5. 1

이렇게 5경우를 확인할 수 있다.