[dfs] 프로그래머스 피로도 문제 풀이

1. 재귀방식 DFS(깊이 우선 탐색) 활용

DFS를 사용하면 모든 방문 순서의 경우를 탐색할 수 있습니다.

1. 현재 던전을 방문할 수 있는지 확인합니다.
2. 방문했다면 피로도를 갱신하고 다음 던전 탐색을 진행합니다.
3. 탐색이 끝난 후 원래 상태로 되돌리는 백트래킹을 수행합니다.

2. 반복문을 활용한 DFS (스택을 사용한 방법)

재귀 호출 없이 반복문과 스택을 활용하여 DFS를 구현할 수도 있습니다.

1. stack을 사용하여 DFS 탐색 상태(현재 피로도, 방문한 던전 개수, 방문 여부)를 저장합니다.
2. DFS처럼 탐색을 진행하되, 탐색 상태를 스택에 저장하면서 모든 경로를 탐색합니다.
3. 최대로 방문할 수 있는 던전 개수를 구합니다.

---

DFS 재귀 풀이

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

  function dfs(k, visitCount) {
    maxVisitCount = Math.max(maxVisitCount, visitCount);

    for (let i = 0; i < dungeons.length; i++) {
      if (!visited[i] && k >= dungeons[i][0]) {
        visited[i] = true; // 방문 처리
        dfs(k - dungeons[i][1], visitCount + 1);
        visited[i] = false; // 백트래킹 (다른 경로를 탐색하기 위해 복구)
      }
    }
  }

  dfs(k, 0);
  return maxVisitCount;
}

// 테스트 실행
console.log(
  solution(80, [
    [80, 20],
    [50, 40],
    [30, 10],
  ])
); // ✅ 예상 결과: 3

---

반복문을 활용한 DFS (스택 활용)

function solution_iterative(k, dungeons) {
  let maxVisitCount = 0;
  let stack = [[k, 0, Array(dungeons.length).fill(false)]];

  while (stack.length) {
    let [currentFatigue, count, visited] = stack.pop();
    maxVisitCount = Math.max(maxVisitCount, count);

    for (let i = 0; i < dungeons.length; i++) {
      if (!visited[i] && currentFatigue >= dungeons[i][0]) {
        let newVisited = [...visited]; // 방문 배열 복사
        newVisited[i] = true;
        stack.push([currentFatigue - dungeons[i][1], count + 1, newVisited]);
      }
    }
  }

  return maxVisitCount;
}

// 테스트 실행
console.log(
  solution_iterative(80, [
    [80, 20],
    [50, 40],
    [30, 10],
  ])
); // ✅ 예상 결과: 3

---

❌ 트러블 슈팅: let 없이 for문을 사용했을 때 발생한 문제

DFS를 구현하는 과정에서 for 루프에서 let을 사용하지 않은 코드가 문제가 되었습니다.

🛠️ 문제 코드

function solution2(k, dungeons) {
  let maxVisitCount = 0;
  let visited = Array(dungeons.length).fill(false);

  function dfs(k, visitCount) {
    maxVisitCount = Math.max(maxVisitCount, visitCount);

    for (i = 0; i < dungeons.length; i++) { // ❌ let이 없음
      if (!visited[i] && k >= dungeons[i][0]) {
        visited[i] = true;
        dfs(k - dungeons[i][1], visitCount + 1);
        visited[i] = false;
      }
    }
  }

  dfs(k, 0);
  return maxVisitCount;
}

🔥 문제 발생

• for (i = 0; i < dungeons.length; i++)에서 let이 없어서 전역 변수로 선언됨.
• 다른 곳에서 i를 참조하면 의도치 않게 값이 변경될 위험이 있음.
• 특히 DFS는 재귀적으로 호출되므로 i 값이 꼬일 가능성이 큼.

🚀 해결 방법

• for 루프에서 let을 붙여 지역 변수를 명확히 지정하면 해결됩니다.

function solution2(k, dungeons) {
  let maxVisitCount = 0;
  let visited = Array(dungeons.length).fill(false);

  function dfs(k, visitCount) {
    maxVisitCount = Math.max(maxVisitCount, visitCount);

    for (let i = 0; i < dungeons.length; i++) { // ✅ let 추가!
      if (!visited[i] && k >= dungeons[i][0]) {
        visited[i] = true;
        dfs(k - dungeons[i][1], visitCount + 1);
        visited[i] = false;
      }
    }
  }

  dfs(k, 0);
  return maxVisitCount;
}

---