99클럽 코테 스터디 TLI 22일차-(완전탐색)

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42839

🚨오늘의 학습🚨

⭐️완전탐색 + 백트랙킹⭐️

순열
백트랙킹을 통해 상태복원 필수!!
다른 경우 고려가능

🗝️ 백트랙킹(상태복원)
현재 시도에서 가능한 경우탐색 후 현재 시도의 진행 여부 Reset
다음 시도에서 재사용 가능하도록 함

❓우선순위 큐❓

1. 던전 통과시 필요한 최소 피로도와 소모 피로도에 따른 그리디를 통해 해결하려고 시도함
2. 그래서 최소 피로도와 소모 피로도에 따라 정렬기준을 세움
   최소피로도(내림차순), 소모 피로도(오름차순)
3. 최적의 경우가 아닌경우 발생 (최소 피로도(↓), 소모 피로도(↑) 던전의 경우)

🔅 우선순위 큐는 그리디 방식에 적합
위의 문제의 경우 모든 경우를 탐색 하고 그중 최적의 경로를 찾아야 하므로 DFS 더 적합

---

우선순위 큐

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class P_Dungeons {


    /**
     * 우선순위 큐  =  그리디에 적합
     *
     * 아래의 문제는 완전탐색 = dfs
     * */
    public static int p ;

    public static class Dungeon implements Comparable<Dungeon> {

        int min;
        int spend;


        public Dungeon(int min, int spend) {
            this.min = min;
            this.spend = spend;
        }

        @Override
        public int compareTo(Dungeon dungeon) {

            if (this.min < p && dungeon.min < p) {
                return this.spend - dungeon.spend;
            }
            return dungeon.min - this.min;

        }
    }

    public static void main(String[] args) {

        int result = solution( 80,new int[][]{{80,20},{50,40},{30,10}});
        System.out.print("결과 : "+result);



    }


    public static int solution(int k, int[][] dungeons) {
        p=k;
        int cnt = 0;

        Dungeon[] playList = new Dungeon[dungeons.length];

        for(int i=0; i< dungeons.length; i++){
            playList[i]= new Dungeon(dungeons[i][0], dungeons[i][1]);
        }

        Arrays.sort(playList);

        PriorityQueue<Dungeon> pq = new PriorityQueue<>();

        for (Dungeon dungeon : playList) {
            pq.add(dungeon);
        }


        while(!pq.isEmpty()){
            if(k<pq.peek().min || k<pq.peek().spend){
                break;
            }
            k-=pq.peek().spend;
            pq.poll();
            cnt ++;
        }
        return cnt;

    }

}

---

DFS+백트랙킹

import java.util.Arrays;
import java.util.PriorityQueue;

public class P_Dungeons_2 {

    /**
     * 완전탐색 = dfs
     *
     * 1. 모든 경우의 수 탐색 - dfs
     * 2. 조건에 맞지 않는 경우 소거
     * */

    static int steps=0;

    static int dungeonsCnt;

    public static void main(String[] args) {

        int result = solution( 80,new int[][]{{80,20},{50,40},{30,10}});
        System.out.print("결과 : "+result);

    }


    public static int solution(int k, int[][] dungeons) {

        dungeonsCnt = dungeons.length;


        for(int i=0; i<dungeonsCnt; i++){

            int[] visited = new int[dungeonsCnt];
            int cnt = 0;
            int p = k;

            dfs(dungeons,i,visited,cnt,p);
        }


        return steps;

    }

    public static void dfs(int[][] dungeons, int i,int[] visited, int cnt, int p){
        if(cnt>dungeonsCnt){
            return;
        }

        if(dungeons[i][0]<=p && dungeons[i][1]<=p){
            visited[i] = 1;
            p-=dungeons[i][1];
            cnt ++;

            if(Integer.compare(cnt,steps)==1){
                steps = cnt;
            };

            for(int j=0; j<dungeons.length; j++){
                if(visited[j]==1){
                    continue;
                }

                if(p>=dungeons[j][0] && p>=dungeons[j][1]){

                    dfs(dungeons,j,visited,cnt, p);


                }

            }
            visited[i]=0;

        }


    }

}