[프로그래머스] JS알고리즘 - 피로도

오늘은 프로그래머스 2단계 <피로도>를 완전탐색으로 푸는 방법에 대한 내용을 포스팅해보려 합니다.

 

 

 

문제 설명

 

XX게임의 피로도 시스템과 던전 탐험 메커니즘을 이해하는 것이 이번 문제의 핵심입니다. 각 던전은 '최소 필요 피로도'와 '소모 피로도'를 가지고 있으며, 이를 통해 유저가 탐험할 수 있는 최대 던전 수를 계산해야 합니다.

 

 

 

 

문제

 

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다.

 

각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다. 이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

 

 

 

 

풀이 방법

 

백트래킹을 이용한 완전탐색 방법을 사용합니다. 백트래킹은 가능한 모든 조합을 시도하면서 해결책을 찾는 방식입니다. 여기서는 유저가 탐험할 수 있는 던전의 조합을 찾습니다.

function solution(k, dungeons) {
    // 백트래킹을 위한 함수
    function explore(remainingStamina, visited) {
        let maxCount = 0;
        for (let i = 0; i < dungeons.length; i++) {
           // console.log(`dungeons[i]: ${dungeons[i]}, remainingStamina: ${remainingStamina}, visited[i]: ${visited[i]}`)
            if (!visited[i] && remainingStamina >= dungeons[i][0]) {
                // 현재 던전 방문
                visited[i] = true;
                // 남은 피로도 계산
                let newStamina = remainingStamina - dungeons[i][1];
                // 다음 던전 탐색
                let count = explore(newStamina, visited) + 1;
                // 최대 탐험 가능한 던전 수 갱신
                maxCount = Math.max(maxCount, count);
                // 던전 방문 초기화 (백트래킹)
                visited[i] = false;
            }
        }
        return maxCount;
    }

    // 모든 던전에 대해 방문 여부를 추적하는 배열
    let visited = new Array(dungeons.length).fill(false);
    // 최대 탐험 가능한 던전 수 계산
    return explore(k, visited);
}

 

 

 

 

실행결과

위 코드는 재귀 호출, 최대 탐험 가능한 던전 수 갱신, 백트래킹을 포함하여 문제를 해결합니다.

이를 통해 모든 가능한 던전 조합을 효과적으로 탐색할 수 있습니다.

위 코드는 아래와 같은 사항들을 담고 있습니다.

 

1. 재귀 호출 (let count = explore(newStamina, visited) + 1;):

 

- explore 함수는 현재 던전을 탐험한 후 남은 피로도(newStamina)와 현재까지 방문한 던전 상태(visited)를 기반으로 다음 던전 탐색을 계속합니다.

- 이 함수는 탐험할 수 있는 던전의 최대 수를 반환합니다.

- 현재 던전도 탐험한 것으로 간주하므로, 반환된 값에 1을 더합니다 (+ 1).

 

 

2. 최대 탐험 가능한 던전 수 갱신 (maxCount = Math.max(maxCount, count);

- maxCount 변수는 현재까지 탐험한 최대 던전 수를 저장합니다.

- Math.max 함수를 사용하여, 이전의 최대값(maxCount)과 새로 계산된 값(count) 중 더 큰 값을 maxCount에 저장합니다.

 

 

3. 던전 방문 초기화 - 백트래킹 (visited[i] = false;):

- 현재 던전에 대한 탐색이 끝나면, visited[i]를 false로 설정하여 던전 방문 상태를 초기화합니다.

- 이는 백트래킹의 일부로, 다음 재귀 호출에서 다른 던전 조합을 탐색할 수 있도록 합니다.

- 백트래킹은 예를들어 아래와 같은 순서로 이루어집니다.

- 시작: 모든 던전은 방문하지 않은 상태로 시작합니다. (A: 방문 안 함, B: 방문 안 함, C: 방문 안 함)

- 던전 A 방문: A를 방문하면, A는 방문한 상태가 됩니다. (A: 방문 함, B: 방문 안 함, C: 방문 안 함)

- 다음 던전 선택: 이제 B와 C 중에서 선택할 수 있습니다.

- B를 선택한 경우: (A: 방문 함, B: 방문 함, C: 방문 안 함)

- C를 선택한 경우: (A: 방문 함, B: 방문 안 함, C: 방문 함)

- 백트래킹: A와 B를 방문한 후, 다시 A로 돌아와 B의 방문 상태를 초기화합니다. (A: 방문 함, B: 방문 안 함, C: 방문 안 함)

- 새로운 조합 탐색: 이제 A와 C를 탐험하는 조합을 탐색할 수 있습니다.

 

 

 

이 문제는 백트래킹을 통해 모든 가능한 던전 조합을 탐색함으로써 해결할 수 있습니다. 간단해 보이지만, 다양한 아이디어와 연습이 필요한 문제입니다.