[JAVA] 완전탐색 : 피로도

1. 문제 내용

요약
현재 내 피로도와 2차원 배열에 최소 입장 피로도와 입장시 소모 피로도가 입력된다
현재 내 피로도로 던전 최대한 많이 던전에 들어갈 수 있는 수를 출력하라

2. 접근 방법
 모든 배열의 값들을 순차적으로 전부 비교하여 입장 횟수가 가장 높은 값을 출력하면 될 것 같다

3. 구현 과정

Queue<int[]> queue = new LinkedList<>();
for(int i = 0; i < dungeons.length; i++){
	queue.offer(dungeons[i]);
}

순차적으로 비교하기 위한 큐를 생성해 던전배열을 저장

public int search(Queue<int[]> queue, int k, int count){
        if(queue.isEmpty()) return count;
        int length = queue.size();
        int inCount = count;
        int inK = k;
        for(int i = 0; i < length; i++) {
            int[] dungeon = queue.poll();
            if(inK >= dungeon[0]) {
                inK -= dungeon[1];
                inCount = Math.max(inCount, search(queue, inK, count + 1));
            }
            queue.offer(dungeon);
            inK = k;
        }
        return inCount;
    }

모든 배열의 값을 출발점으로 할 수 있고 출발점 다음의 값을 재귀호출을 하여 큐가 빌때까지 가거나 더이상 진행할 값이 없을 때 까지 반복

4.결과

전체코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int k, int[][] dungeons) {
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < dungeons.length; i++){
            queue.offer(dungeons[i]);
        }
        return search(queue, k, 0);
    }
    public int search(Queue<int[]> queue, int k, int count){
        if(queue.isEmpty()) return count;
        int length = queue.size();
        int inCount = count;
        int inK = k;
        for(int i = 0; i < length; i++) {
            int[] dungeon = queue.poll();
            if(inK >= dungeon[0]) {
                inK -= dungeon[1];
                inCount = Math.max(inCount, search(queue, inK, count + 1));
            }
            queue.offer(dungeon);
            inK = k;
        }
        return inCount;
    }

}