[코딩테스트] 완전탐색 - 피로도

프로그래머스 완전탐색 Lv.2 - 피로도

문제

---

입출력 예시

---

접근 방법

• count를 hashset에 담아 가장 큰 숫자를 반환하자
• 최소 필요 피로도가 존재하는지 확인하는 메서드 생성
• perm 내에서 count가 존재할 때 hashset에 담기
• for문으로 하나의 던전을 지날 때마다 최소 필요 피로도가 일치할 시 k 에서 소모 피로도를 깎는다
• 재귀를 이용하여 순서를 바꿔서 count를 세보자

내 코드

---

class Solution {
    Set<Integer> set = new HashSet<>();
    public int solution(int k, int[][] dungeons) {
        perm(0, dungeons);
        return max;
    }
    
    public boolean checkFatigue(int k, int mink) {
        if (k <= 0) return false;
        if (mink > k) return false;
        return true;
    }
    
    public void perm(int k, int[][] dungeons) {
        int count =0;
        if (count > 0) {
            set.add(count);
        }
        for (int i=0; i < dungeons.length; i++) {
            System.out.printf(i + "\n" + + k + "\n");
            if (checkFatigue(k, dungeons[i][0])) {
                k = k - dungeons[i][1];
                count++;
                perm(k, dungeons[i+1]);
            }
        }
    }
}

실패 이유

---

• 모든 경우의 수를 완전 탐색하지 않았다
• 각각의 순서 당 count를 hashset에 저장하는 것이 적절하지 않다
  - 결과값이 가장 큰 경우가 구해지지 않는다
• 재귀 메소드의 매개변수 값이 적절하지 않다
  - (최소 피로도 메소드가 굳이 필요하지 않다)

-> 순열 방식을 더 고민해보자

• visited 배열을 사용해서 dfs 탐색하기
• dfs를 돌때마다 피로도를 계산하고 횟수 세기
• 횟수들 중 큰 결과값을 answer에 저장

class Solution {
    private static int answer;
    private static boolean visited[];
    public static int solution(int k, int[][] dungeons) {
        answer = 0;
        visited = new boolean[dungeons.length];
        dfs(0, k, dungeons, 0);
        return answer;
    }
    
    
    public static void dfs(int depth, int k, int[][] dungeons, int ans) {
        //System.out.println("ans :" + ans);
        //System.out.println("answer :" + answer);
        if (depth >= dungeons.length) { 
            if (ans > answer) { 
                answer = ans;
            }      
        }
        
        for (int i = 0; i < dungeons.length; i++) {
            //System.out.println("i :" + i);
            //System.out.println("depth: " + depth);
            //System.out.println("k :" + k);
			if (visited[i]) {
				continue;
			}
			visited[i] = true;
			if (k >= dungeons[i][0]) {
				dfs(depth + 1, k - dungeons[i][1], dungeons, ans + 1);
			} else {
				dfs(depth + 1, k, dungeons, ans);
			}
			visited[i] = false;
		}
    }
}

디버깅 출력

---

answer :0
depth: 0
k :80
answer :0
depth: 1
k :60
depth: 1
k :60
answer :0
depth: 2
k :20
depth: 2
k :20
depth: 2
k :20
answer :0
depth: 3
k :20
depth: 3
k :20
depth: 3
k :20
depth: 1
k :60
answer :2
depth: 2
k :50
depth: 2
k :50
answer :2
depth: 3
k :10
depth: 3
k :10
depth: 3
k :10
depth: 2
k :50
depth: 0
k :80
answer :3
depth: 1
k :40
answer :3
depth: 2
k :40
depth: 2
k :40
depth: 2
k :40
answer :3
depth: 3
k :30
depth: 3
k :30
depth: 3
k :30
depth: 1
k :40
depth: 1
k :40
answer :3
depth: 2
k :30
answer :3
depth: 3
k :30
depth: 3
k :30
depth: 3
k :30
depth: 2
k :30
depth: 2
k :30
depth: 0
k :80
answer :3
depth: 1
k :70
answer :3
depth: 2
k :70
depth: 2
k :70
answer :3
depth: 3
k :30
depth: 3
k :30
depth: 3
k :30
depth: 2
k :70
depth: 1
k :70
answer :3
depth: 2
k :30
answer :3
depth: 3
k :30
depth: 3
k :30
depth: 3
k :30
depth: 2
k :30
depth: 2
k :30
depth: 1
k :70

참고

https://bcp0109.tistory.com/14