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

 

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/87946

[ 요약 ]

시작 시간 : .

종료 시간 : .

소요 시간(분) : .

 

도전 횟수 (제출 횟수) : .

로직 및 풀이 참고 여부 : O

 

[ 풀어보기 ]

 

풀이

📌 로직

1. 여러가지를 고려해보았으나 다 실패했다.
   
   • 최소 필요 피로도가 높은 것부터 통과하기
   • 소모 피로도가 낮은 것 부터 통과하기
   • 최소 필요 피로도 - 소모 피로도의 값을 구한 후, 값이 큰 것부터 통과하기
2. 그러니.. 완전 탐색을 활용하는 수 밖에 없다. (문제 분류가 완전탐색인 이유가 있었다...)
   
   • 방문 여부를 체크하는 boolean 배열변수 visited를 전역변수로 선언
   • 방문할 수 있는 던전의 최대 개수를 담을 변수 int max를 전역변수로 선언
   • dungeons의 처음부터 끝까지 순회하는 for문을 생성한다.
   • 현재 방문한 던전의 위치에 해당하는 visitied를 true로 초기화,
     현재 체력에서 소모 피로도만큼 빼기.
     방문한 던전의 개수를 +1
   • 다음으로 들릴 던전을 찾기 위해 dungeons 배열의 0부터 끝까지 탐색하는 for문 다시 생성.
   • 만약 visited가 false이고, 현재 체력보다 최소 필요 피로도가 낮은 던전이 있다면, 위 과정 반복
   • 한 루트를 다 탐색한 후, 해당 루트의 던전 방문 개수가 max보다 더 크다면
     그 값을 max로 갱신하기
3. 참고
   • https://katastrophe.tistory.com/59

 

📌 코드

// 피로도고 뭐고 내가 잠온다...
import java.util.*;

class Solution {
    boolean[] visited;
    int[][] dungeons;
    int max;
    
    public int solution(int k, int[][] dungeons) {
        int answer = 0;
        this.dungeons = dungeons;
        visited = new boolean[dungeons.length];
        
        for(int i=0; i<dungeons.length; i++) {
            if(k>=dungeons[i][0]) dfs(i, k, 1);
        }

        return max;
    }
    
    private void dfs(int current, int tired, int depth) {
        // current 현재 탐색하는 위치
        // tired 현재 피로도
        // depth 현재 깊이
        
        visited[current] = true;
        tired -= dungeons[current][1];
        for(int i=0; i<dungeons.length; i++) {
            if(!visited[i] && dungeons[i][0] <= tired)
                dfs(i, tired, depth+1);
        }
        max = Math.max(max, depth);
        visited[current] = false;
    }

}

 

📌 채점 결과

정확성  테스트
테스트 1 〉	통과 (0.05ms, 74.3MB)
테스트 2 〉	통과 (0.04ms, 76.3MB)
테스트 3 〉	통과 (0.04ms, 71.7MB)
테스트 4 〉	통과 (0.17ms, 83.2MB)
테스트 5 〉	통과 (0.33ms, 76.9MB)
테스트 6 〉	통과 (0.83ms, 76.5MB)
테스트 7 〉	통과 (2.00ms, 75.3MB)
테스트 8 〉	통과 (2.91ms, 80.5MB)
테스트 9 〉	통과 (0.05ms, 71.4MB)
테스트 10 〉	통과 (0.44ms, 70.9MB)
테스트 11 〉	통과 (0.05ms, 79.7MB)
테스트 12 〉	통과 (0.54ms, 73.7MB)
테스트 13 〉	통과 (0.13ms, 73.6MB)
테스트 14 〉	통과 (0.12ms, 78.3MB)
테스트 15 〉	통과 (0.04ms, 74.3MB)
테스트 16 〉	통과 (0.05ms, 77.4MB)
테스트 17 〉	통과 (0.06ms, 77.4MB)
테스트 18 〉	통과 (0.04ms, 76MB)
테스트 19 〉	통과 (0.10ms, 74.2MB)

채점 결과
정확성: 100.0
합계: 100.0 / 100.0

 

---

[배운 점]

 

📌 배운 것

1. 깊이 우선 탐색 DFS의 개념
   
   • https://eunzzzzz1.tistory.com/39

     [그래프 탐색] DFS (Depth First Search, 깊이 우선 탐색)

2. 배운점 2
   • 설명2