[프로그래머스] 피로도-level2-dfs

📌 문제

프로그래머스 | level2 | 완전탐색

https://school.programmers.co.kr/learn/courses/30/lessons/87946#qna

프로그래머스

 

 

📌 문제 탐색하기

• 최소 필요 피로도 : 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도
• 소모 피로도 : 던전을 탐험한 후 소모되는 피로

ex) 최소 필요 피로도 80, 소모 피로도 20 인 던전 ⇒ 사용자의 피로도 ≥ 80 & 던전 이후 피로도 - 20

• 하루 한번씩 탐험할 수 있는 던전 여러개

 

📌 알고리즘

• 유저가 이 던전을 최대한 많이 탐험하려고 함 ⇒ 완전탐색 BFS/DFS
• 유저의 현재 피로도 K는 5000이하의 자연수
• 던전의 개수는 8개
• 던전[최소필요피로도, 소모피로도] 는 모두 1000이하의 자연수

⇒ 그러면 가능한 가지수가 8! ⇒ 40320가지수

O(N!)이므로 BFS/DFS 풀이가 가능하다.

 

 

📌 코드 설계하기

1. 던전의 크기에 따라 for문으로 돌면서 bfs 탐색 진행하기
2. visited를 통해서 이미 지나간 던전은 예외표시하기

 

 

📌 시도 회차 수정 사항 (Optional)

1회차

• 초기에 무조건 던전을 다 돌아야한다고 생각했었는데 문제를 다시 생각해보니 ‘최대 던전 도는 횟수’를 구하는 것이므로 1회차 실패

 

2회차

• 결국에는 백트래킹 기법을 활용해서 DFS로 해결 가능

 

 

📌 백트래킹 VS DFS

백트래킹

• DFS 기반으로 진행
• BUT, 탐색 과정에서 조건을 만족하지 않는 경로를 미리 배제
• OR 상태를 복구하며 진행하는 방식

 

DFS

• 탐색할 수 있는 한 최대한 깊이 탐색 후, 더 이상 진행할 수 없을 때 되돌아 오는 탐색방식
• 상태 복구 여부와 상관 없이, ‘깊이’를 우선시 하는 것 자체가 DFS
• 공간복잡도 면에서, dfs는 가지치기 없이 모든 경우를 다 확인하므로 백트래킹보다 안 좋을 수 있다.

 

 

📌 정답 코드 비교

### DFS + 백트래킹 ### 
import java.util.*;
import java.io.*;

class Solution {
    static int answer = 0;
    static int[] visited; 
    public int solution(int k, int[][] dungeons) {
        visited = new int[dungeons.length];
        dfs(dungeons, k, 0);
        
        return answer;
    }
    public void dfs(int[][] dungeons, int k, int depth){
        if(depth > answer){
            answer = Math.max(answer,depth);
            return;
        }
            
        for(int i = 0; i<dungeons.length; i++){
            if(visited[i] == 0 && k - dungeons[i][0] >= 0){ //가지치기 (pruning)
                visited[i] = 1;
                k -= dungeons[i][1];
                depth+=1;
                dfs(dungeons, k, depth);
                k += dungeons[i][1];
                visited[i] = 0;
                depth-=1;
            } 
        }
    }
}

### DFS ###
import java.util.*;
import java.io.*;

class Solution {
    static int answer = 0;
    static int[] visited;
    public int solution(int k, int[][] dungeons) {
        visited = new int[dungeons.length];
        dfs(dungeons, k, visited, 0);
        return answer;
    }
    
    public void dfs(int[][] dungeons, int k, int[] visited, int depth){
        if(depth > answer){
            answer = depth;
        }
        for(int i = 0; i< dungeons.length; i++){
            if(visited[i] == 0 && k >= dungeons[i][0]){
                visited[i] = 1;
                dfs(dungeons, k-dungeons[i][1], visited, depth+1);
                visited[i] = 0;
            }
        }
        
    }
}