[Programmers Level 2] 피로도 Javascript

⚡문제정보

제 통곡의 벽인 완전탐색을 해야하는 문제입니다.

k라는 내 초기 피로도가 주어지고

던전을 최대한 많이 돌아야하는 건데 이건 던파 많이해보신 분들은 아시겠지만

피로도를 극한까지 아꼈다가 최대한 소모피로도가 큰 던전을 가는게 제일 이득이죠

 

가장 많은 던전을 방문할 수 있는 경우의 수를 찾아야하는 문제인데

여기서 최소 필요 피로도라는 개념이 있어서 내 현재 피로도가

최소 필요 피로도보다 낮으면 던전에 방문할 수 없는 제한조건까지 걸려있습니다.

 

조건이 까다로우니 탐욕법같은건 적용하기 애매하겠고

그냥 맘편히 다 찾아보는게 제일 답을 찾기 좋겠네요

조건을 보면 던전의 최대 갯수도 8개뿐이니까 충분히 완전탐색을 돌릴만 해보입니다. 

---

🔍접근방법

다 푼 사람의 블로그를 참고한다.
https://leejams.github.io/%ED%94%BC%EB%A1%9C%EB%8F%84/

---

😑다른 분의 풀이

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

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

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

  DFS(k, 0);

  return answer;
}

한줄 한줄 씩 보면 dfs 기본 문제 풀때랑 크게 다르지 않은 느낌이네요

  let answer = 0;
  const visited = new Array(dungeons.length).fill(false)

답을 저장해줄 answer 변수와

visited를 체크해줄 변수를 만들어줍니다.

어차피 배열이라 const로 선언해도 요소는 수정가능

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

중첩함수로 DFS를 수행할 함수를 만들어주고

for문을 visited할 노드의 갯수만큼 반복하도록 코드를 작성

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

DFS를 시행할 if문을 작성합니다.

방문하지 않은 노드이면서 / 현재 남은 피로도가 최소 요구 피로도보다 큰 경우엔

순회를 해야할 노드일것입니다.

이 경우 visited[i] = true로 할당해주는 것으로

현재 방문중인 dungeons[i]를 true로 만들어준 뒤

(이 작업으로 인해 재귀호출의 for문에서 현재 방문중인 던전을 중복 방문하는 경우를 없앨 수 있습니다.)

 

그리고 현재 피로도에서 현재 방문중인 던전의 피로도를 빼준 뒤

방문한 던전의 카운트를 1 높여서 재귀호출 해줍니다.

 

이렇게 모든 노드에 대한 탐색이 끝나고 재귀호출이 다시 위로 올라와서

초기의 for문으로 돌아오면

현재 visited[i]를 다시 false로 바꿔주고 다음 for문을 돌립니다.

(이 작업을 통해 매 for문마다 다른 노드들이 전부 false인 상태로 작업을 할 수 있게됩니다.)

 

    answer = Math.max(answer, L);

재귀의 바닥부분에서 L값과 현재 answer값을 비교하여 더 큰값을 answer에 할당해줍니다.

이 작업을 모든 경우의 수를 다 탐색할때까지

(i = dungeons.length- 1일때까지) 반복하면 모든 경우의 수를 다 탐색하게되고

그 결과 얻은 L값이 최대 값일 것입니다.

  DFS(k, 0);

  return answer;

따라서 중첩함수를 호출해준 뒤

위 과정을 반복해서 얻어낸 answer를 반환하면 끝입니다.

---

😑풀이를 안보고 다시 풀기

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

오케이... 몇번만 더...해보면.... 어케...안될까..?