[Day22]JAVA 프로그래머스 피로도(완전탐색)

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

프로그래머스

 

 

프로그래머스 피로도 문제는 완전탐색 방식을 활용하여 해결할 수 있다. 

---

🌘문제 이해하기 

 

• 한 유저의 피로도 :   K
• 던전 의 각 행은 [ "최소 필요 피로도" , "소모 필요 피로도" ] 로 저장되어 있다.
•  "최소필요 피로도" 는 항상 "소모 피로도" 보다 크거나 같다. 
• 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

던전을 탐험 할때마다 K - 소모필요 피로도 가 소진되고 

유저의 남은 피로도는 다음 던전의 "최소 필요 피로도" 이상은 남아 있어야 방문 가능하다. 

 

완전 탐색은 모든 로직은 다 탐색하여 그 중 최적의 값을 고르는 것이다.

던전을 탐험할 수 있는 모든 경로로 탐험을 하고 그 중 유저가 탐험할 수 있는 최대 던전 수가 결과 값이다. 

 

---

🌗 문제 자세히보기

 

k = 80 
dungeons = [[80,20],[50,40],[30,10]]

 

던전을 탐험하는 방법은 재귀함수를 사용하여 탐험할 수 있는 다음 던전으로 이동하는 것이다.

 

1. 처음 던전[80,20] 을 방문하려면 "최소 필요 소모도"는 80 가 있어야 한다. 

• k >= dungeons. 최소필요소모도

2. 적합하면 해당 던전으로 탐험(visited  = true) 남은 소모도는 80 - 20 = 60

3. 두번째 던전[50,40] 을 방문하려면 "최소 필요 소모도"는 50 이 있어야 한다 

•  60 > 50  현재 남은 소모도가 "최소 필요 소모도" 크므로 탐험 (visited  = true) 남은 소모도는 60 - 40 = 20

4. 세번재 던전[30,10] 탐험하려면 현재 남은 소모도가 30이상은 있어야 하는데 현재 남은 소모도는 10 이므로 탐험 불가 

5. 이제 더이상 탐험할 던전이 없으므로 돌아간다. 

6. 재귀호출 했던 것들을 다시 돌아간다. 

.. 

해당 과정들은 반복하여 유저가 탐험할 수 있는 최대 던전 수를 구한다.

 

처음에 재귀호출 과정이 헷갈려서 직접 매 순간 출력하여 재귀함수 호출 흐름을 따라가 보았다. 

for(int i=0;i<dungeons.length;i++)
{
    // 던전에 방문한 적 없고 , 현재 사용자 피로도 > 최소필요 피로도
    System.out.println("<<<" + i + ">>>>  던전 방문여부 : " + visited[i]);
    if(!visited[i] && dungeons[i][0] <=k)
    {
        System.out.println("["+i+"]"+"던전탐색 : "+ (count+1) + "| 현재 소모도 "+k+" , 필요소모도 : " +dungeons[i][0] + " , 소요소모도: " + dungeons[i][1] + ", 남은소모도: " + (k -dungeons[i][1]));
        visited[i] = true; //던전방문
        DFS(dungeons, visited, count+1 ,k -dungeons[i][1]);
        System.out.println((i)+"로 다시돌려~");
        visited[i] = false; // 재귀함수 끝나면 던전 다시 방문 끝남
        System.out.println(i+"던전 방문 취소");
    }
}

 

결과값 : 

<<<0>>>>  던전 방문여부 : false
[0]던전탐색 : 1| 현재 소모도 80 , 필요소모도 : 80 , 소요소모도: 20, 남은소모도: 60
<<<0>>>>  던전 방문여부 : true
<<<1>>>>  던전 방문여부 : false
[1]던전탐색 : 2| 현재 소모도 60 , 필요소모도 : 50 , 소요소모도: 40, 남은소모도: 20
<<<0>>>>  던전 방문여부 : true
<<<1>>>>  던전 방문여부 : true
<<<2>>>>  던전 방문여부 : false
1로 다시돌려~
1던전 방문 취소
<<<2>>>>  던전 방문여부 : false
[2]던전탐색 : 2| 현재 소모도 60 , 필요소모도 : 30 , 소요소모도: 10, 남은소모도: 50
<<<0>>>>  던전 방문여부 : true
<<<1>>>>  던전 방문여부 : false
[1]던전탐색 : 3| 현재 소모도 50 , 필요소모도 : 50 , 소요소모도: 40, 남은소모도: 10
<<<0>>>>  던전 방문여부 : true
<<<1>>>>  던전 방문여부 : true
<<<2>>>>  던전 방문여부 : true
1로 다시돌려~
1던전 방문 취소
<<<2>>>>  던전 방문여부 : true
2로 다시돌려~
2던전 방문 취소
0로 다시돌려~
0던전 방문 취소
<<<1>>>>  던전 방문여부 : false
[1]던전탐색 : 1| 현재 소모도 80 , 필요소모도 : 50 , 소요소모도: 40, 남은소모도: 40
<<<0>>>>  던전 방문여부 : false
<<<1>>>>  던전 방문여부 : true
<<<2>>>>  던전 방문여부 : false
[2]던전탐색 : 2| 현재 소모도 40 , 필요소모도 : 30 , 소요소모도: 10, 남은소모도: 30
<<<0>>>>  던전 방문여부 : false
<<<1>>>>  던전 방문여부 : true
<<<2>>>>  던전 방문여부 : true
2로 다시돌려~
2던전 방문 취소
1로 다시돌려~
1던전 방문 취소
<<<2>>>>  던전 방문여부 : false
[2]던전탐색 : 1| 현재 소모도 80 , 필요소모도 : 30 , 소요소모도: 10, 남은소모도: 70
<<<0>>>>  던전 방문여부 : false
<<<1>>>>  던전 방문여부 : false
[1]던전탐색 : 2| 현재 소모도 70 , 필요소모도 : 50 , 소요소모도: 40, 남은소모도: 30
<<<0>>>>  던전 방문여부 : false
<<<1>>>>  던전 방문여부 : true
<<<2>>>>  던전 방문여부 : true
1로 다시돌려~
1던전 방문 취소
<<<2>>>>  던전 방문여부 : true
2로 다시돌려~
2던전 방문 취소

 

🌕 최종코드 

 

class Solution {
    static int answer = -1;
    public int solution(int k, int[][] dungeons) {
      
        //던전 방문배열 생성
        boolean[] visited = new boolean[dungeons.length];
        
        DFS(dungeons, visited, 0 ,k);
        
        return answer;
    }
    
    //완전탐색(모든 경우를 다 구해고 그 중 최적의 답을 채택)
    public void DFS(int[][] dungeons,boolean[] visited , int count , int k)
    {        
        answer = Math.max(answer, count);
        
        //던전을 방문 시작
        for(int i=0;i<dungeons.length;i++)
        {
             //방문한적이 있거나 현재 남아있는 피로도가 최소필요 피로도보다 크면 방문할 수 있다. 
            if(!visited[i] &&  dungeons[i][0] <=k)
            {
                //방문 할 때마다  count늘리기
                visited[i] = true;
                // 다음 던전 탐색하기
                DFS(dungeons,visited,count+1,k-dungeons[i][1]);
                visited[i] = false;                
            }
        }
    }
    
}