[알고리즘JS] 피로도 (프로그래머스 lv.2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/87946

풀이

• DFS 를 이용한 완전탐색으로 접근하면 풀 수 있는 문제.
• 처음에는 이중 반복문으로 탐색하려고 했는데, 순열 문제임을 알았음에도 반복문을 써서 정답을 도출할 수 없었다.
• 이중 반복문을 사용하면, 0-1-2, 1-0-1, 2-0-1 처럼 정해진 순서밖에 돌지 못하기 때문에 DFS 로 접근해야 한다.

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

  const DFS = (fatigue, count) => {
    answer.push(count);

    // DFS의 출발 지점 : 1번 던전 ~, 2번 던전 ~, 3번 던전~
    for (let L = 0; L < N; L++) {
      // 방문한 적이 없고 피로도가 최소 피로도보다 높다면
      if (!visited[L] && fatigue >= dungeons[L][0]) {
        visited[L] = 1; // 방문 처리
        DFS(fatigue - dungeons[L][1], count + 1); // DFS 호출
        visited[L] = 0; // 다녀왔으므로 방문 해제
      }
    }
  };

  DFS(k, 0);

  return Math.max(...answer);
}

DFS

• DFS 로 순열을 구하게 되면 0 ~ L 에 대하여 완전 탐색을 하면서, 방문하지 않은 요소에 대해서만 재귀를 호출한다.

// n개 중에서 m개를 뽑아 순열 만들기
function ref(m, arr) {
  let answer = '';
  const n = arr.length;
  const visited = new Array(n).fill(0);
  let tmp = new Array(m).fill(0);

  function DFS(L) {
    // m에 도달하면 정답문자열을 추가
    if (L === m) {
      answer += `${tmp}\n`;
    }
    // 반복 조건
    else {
      for (let i = 0; i < n; i++) {
        if (visited[i] === 0) {
          visited[i] = 1;
          tmp[L] = arr[i];
          DFS(L + 1);
          visited[i] = 0;
        }
      }
    }
  }
  DFS(0);
  return answer;
}

let arr = [3, 6, 9];
console.log(ref(2, arr));