[프로그래머스] 프로그래머스 알고리즘: LV2/87946 - 피로도

문제

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

프로그래머스

 

 

나의 풀이

class Solution {
 
    static int n;
    static int max = Integer.MIN_VALUE;
 
    public int solution(int k, int[][] dungeons) {
 
        n = dungeons.length;
 
        boolean[] visit = new boolean[n + 1];
 
        dfs(0, k, dungeons, visit);
 
        return max;
    }
 
    public void dfs(int depth, int sum, int[][] dungeons, boolean[] visit){
 
        max = Math.max(max, depth);
 
        for(int i = 0; i < n; i++){
            if(visit[i + 1] == false && sum >= dungeons[i][0]){
                visit[i + 1] = true;
                dfs(depth + 1, sum - dungeons[i][1], dungeons, visit);
                visit[i + 1] = false;
            }
        }
    }
}

내가 생각했던 풀이과정

대표 알고리즘: dfs(백트래킹)

1. 최대 깊이를 어디까지 갔는지를 구하는 문제이다.
2. 순서 없이 방문할 수 있기 때문에( 1 → 3 → 2) 방문 여부를 트래킹하면서 dfs로 풀어야한다.
3. dfs를 할 때는 방문하지 않았고 피로도가 던전의 최소 피로도보다 클 경우 방문할 수 있다
4. 방문을 할 경우에는 방문 체크와 함께 ( 피로도 - 던전 입장 피로도) 를 빼줘야한다
5. 방문을 한 이후에는 추후 다른 경우에서 방문할 수 있도록 방문 여부를 해제해준다
   1. ex) 1 → 2 → 3, 1 → 3 → 2 / 2 → 1 → 3, 2 → 3 → 1

다른 사람의 풀이

 

새로 알게된 점, 확인해야할 점

순서와 관계없이 방문 하기를 원한다면 방문 여부를 반드시 체크하면서 순회를 돌아야한다.