[완전탐색] 프로그래머스 '피로도' - js

1. 문제

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

프로그래머스

2. 코드

처음 푼 코드(부분 정답) 

특정 케이스만 정답처리 되었다. 아마 최소 필요도, 소모 필요도 중 최소 필요도만 신경 쓴 로직이어서 그런 것 같다. 두 개 이상의 조건을 신경 써야 하는 경우에는 전부 다 확인해 줄 수 있도록 완전탐색을 이용해야 하나 보다. 애초에 if문의 조건이 문제인 것 같다. 하나의 던전만 방문하고 나머지 3개의 던전은 방문 못하는 케이스가 있는 경우라면 else문에 있는 로직이 실행될 일이 없어 뒤죽박죽 되어버리는 것 같다. 결론은 방문한 던전에 대한 처리가 필요하다는 것!

function solution(k, dungeons) {
    let ans = 1;
    
    dungeons = dungeons.sort((a, b) => b-a);
    
    const trip = (leftD,leftK) => {
        if(leftD.length >= 1){
            for(let i=0;i<leftD.length;i++){
                if(leftD[i][0] <= leftK){
                    let newK = leftK - leftD[i][1];
                    let newD = [...leftD];
                    newD.splice(i,1);
                    trip(newD,newK);
                }
            }
        }else ans = Math.max(ans,dungeons.length-leftD.length);
    }
    
    trip(dungeons,k);
    
    return ans;
}

정답)

던전 방문 경로를 fixed 해나가며 다음 경로들을 붙히는 유형이기 때문에 이 문제 또한 소수찾기(level 2)의 문제와 마찬가지로 dfs를 사용하는 문제이다. 

 

dfs 파라미터?!

• count : 던전 탐색 깊이를 +1 해나가기 위함
• k : 현재 피로도

 

주의사항! 재귀 함수 아규먼트에서는 전위/후위 연산자는 사용하지 말자! 의도치 않은 현상을 초래할 수 있다. 그냥 +1, -1 이런식으로 직접 더하고 빼주자.

function solution(k, dungeons) {
  // 모든 조합의 던전 탐색 깊이가 든 배열
  let answer = [];
  // 던전 방문 여부
  let visited = Array(dungeons.length).fill(0);

  const dfs = (count,newK) => {
        answer.push(count);
        
        for(let i=0;i<dungeons.length;i++){
            if(newK >= dungeons[i][0] && !visited[i]){
                visited[i] = 1;
                dfs(count+1, newK-dungeons[i][1]);
                // 다음 for문에서 또 그 던전을 방문해야하기 때문에
                // 하나의 fixed 요소에 대한 재귀 끝나면 다시 0으로 원상복귀
                // 0번째 -> 1번째 -> 2번째 끝난 후에는 0 -> 2 -> 1도 검사해보기 때문
                visited[i] = 0;
            }
        }
    }

  dfs(0, k);

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

다른 버전 코드

function solution(k, dungeons) {
    // 방문한 던전을 제외한 나머지 배열, k를 파라미터로 갖는 dfs
    // 던전을 방문할 때마다 방문 깊이를 저장하고 그 저장한 방문 깊이 중 최댓값을 반환하면 됨
    let answer = [];
    dungeons.sort((a,b) => b[0]-a[0]);
    
    const dfs = (newK, newD) => {
        answer.push(dungeons.length - newD.length);
        if(newK > 0){
            for(let i=0;i<newD.length;i++){
                if(newK >= newD[i][0]){
                    let tempK = newK - newD[i][1];
                    let tempD = newD.slice();
                    tempD.splice(i,1);
                    dfs(tempK,tempD);
                } 
            }
        }
    }
    
    dfs(k, dungeons);
    
    return Math.max(...answer);
}

 

복기

3/28
4/13