프로그래머스 LEVEL 2(피로도)

사용 언어 : javascript
해결 날짜 : 2022-10-11
해결 방법 :
1. dfs 이용
  1. 방문하지 않고 남은 피로도가 필요 피로도보다 크다면 방문 처리
  2. dfs(현재 방문값의 피로도 감소 및 탐험 수 증가)
  3. 방문 처리 초기화(전체에 대한 dfs수행을 위함)
  4. 최대값 업데이트
2. 완전 탐색 이용
  1. dungeons에 대한 모든 순열 구함
  2. 모든 순열을 돌며 최대값 업데이트
회고 :
- x

코드

function solution(k, dungeons) {
    let answer = 0;
    const visited = Array.from({length: dungeons.length}, () => false);
        
    const dfs = (fatigue, dungeons, explored) => {
        for (let i = 0; i < dungeons.length; i++) {
            if (!visited[i] && fatigue >= dungeons[i][0]) {
                visited[i] = true;
                dfs(fatigue - dungeons[i][1], dungeons, explored + 1);
                visited[i] = false;
            }
        }
        answer = Math.max(answer, explored);
    }
        
    dfs(k, dungeons, answer);
        
    return answer;
}

const getPermutations = (arr, num) => {
    const results = [];
    if (num === 1) return arr.map(v => [v]);

    arr.forEach((fixed, index, origin) => {
        const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
        const permutations = getPermutations(rest, num - 1);
        const attached = permutations.map(v => [fixed, ...v]);
        results.push(...attached);
    });

    return results;
}

function solution(k, dungeons) {
    let answer = 0;
    const permutations = getPermutations(dungeons, dungeons.length);
        
    for (const permutation of permutations) {
        let temp = 0;
        let fatigue = k;
        for (const dungeon of permutation) {
            if (fatigue >= dungeon[0]) {
                fatigue -= dungeon[1];
                temp++;
            }
        }
        answer = Math.max(answer, temp);
    }
        
    return answer;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges