[프로그래머스 고득점 Kit] 피로도 자바 풀이 및 정답

문제요약)

- 던전 출입에 필요한 피로도, 클리어시 소모되는 피로도 주어짐

- 최대한 많은 던전 돌았을때의 클리어 던전수 리턴

 

주의점)

- X

 

풀이방법)

1. 모든 던전 케이스를 확인해야해서 DFS로 완전탐색

2. 이미 돈 던전은 전역으로 방문 배열 잡기

3. 방문배열, 피로도 등 확인해서 던전 돌 수 있는지 판단

4. 뎁스를 answer에 저장

 

DFS를 통해 완전탐색을 해야하는 유형이 문제인데 풀이가 바로 떠오르지 않아서 던전이 A, B, C 총 3개인 경우로 생각하고 재귀로 들어가는 과정을 그림을 그려보았습니다.

java

닫기 줄바꿈

public class Fatigue {
​​​​static boolean[] visited;
​​​​static int answer = 0;
​​​​static boolean flag;
​​​​public static void main(String[] args) {

​​​​​​​​// 모든 던전 탐험 가능한 경우
​​​​​​​​int k2 = 300;
​​​​​​​​int[][] dungeons2 = {{100, 20}, {150, 30}, {200, 40}};
​​​​​​​​System.out.println(solution(k2, dungeons2));  // 3

​​​​​​​​// 모든 던전 탐험 불가능한 경우
​​​​​​​​int k3 = 80;
​​​​​​​​int[][] dungeons3 = {{100, 30}, {120, 40}, {150, 50}};
​​​​​​​​System.out.println(solution(k3, dungeons3));  // 0

​​​​​​​​// 던전이 한 개인 경우
​​​​​​​​int k4 = 150;
​​​​​​​​int[][] dungeons4 = {{120, 30}};
​​​​​​​​System.out.println(solution(k4, dungeons4));  // 1
​​​​}

​​​​public static int solution(int k, int[][] dungeons) {
​​​​​​​​visited = new boolean[dungeons.length];
​​​​​​​​DFS(0, k, dungeons);
​​​​​​​​return answer;
​​​​}

​​​​public static void DFS(int depth, int remain, int[][] dungeons) {
​​​​​​​​// 이미 모든 던전을 다 돌 수 있는 케이스를 찾았다면 더 진행할 필요x
​​​​​​​​if (flag) {
​​​​​​​​​​​​return;
​​​​​​​​}
​​​​​​​​// 오면 일단 던전 다 돌기
​​​​​​​​for (int i=0; i<dungeons.length; i++) {
​​​​​​​​​​​​// 방문했거나 피로도가 부족하면 해당 던전 건너뛰기
​​​​​​​​​​​​if (visited[i] || remain - dungeons[i][0] < 0) {
​​​​​​​​​​​​​​​​continue;
​​​​​​​​​​​​}

​​​​​​​​​​​​// 방문 가능하면 방문하면서 다음 뎁스로 넘어가기
​​​​​​​​​​​​visited[i] = true;
​​​​​​​​​​​​int cost = dungeons[i][1];
​​​​​​​​​​​​DFS(depth + 1, remain - cost, dungeons);
​​​​​​​​​​​​visited[i] = false;
​​​​​​​​}

​​​​​​​​answer = Math.max(answer, depth);
​​​​​​​​if (answer == dungeons.length) flag = true;
​​​​}

}