프로그래머스) 피로도

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

프로그래머스

이번 문제는 완전탐색(dfs)를 사용하는 문제이다. 

문제에서 명시를 해놔서 망정이지 dfs를 몰랐던 나에게는 귀중한 시간을 날려버릴뻔했다.

 

문제 풀이에 앞서 dfs를 어떻게 적용했는지 살펴보자. 아직도 dfs는 생초짜이기 때문에 다른 분들의 코드도 많이 참고했음을 이해바란다.

// 1차 고민
1. 피도로 k와 dungeons[i][0]을 비교하고 k가 많으면 진행한다.
2. 진행하면서 k - dungons[i][1]을 해주고 던전에 들어간수 depth에 +1을 해준다.
3. 이를 재귀적으로 반복한다.

// 2차 고민
1. 같은 곳을 두번들어가면 안되기 때문에 방문 표시를 할 수 있는 배열을 선언한다. 
이 배열은 dungeons.lnegth 와 같다.
2. dfs함수를 선언해 이 함수를 계속해서 호출하도록 한다.
3. depth를 계속해서 업데이트 해서 가장 깊이 들어간 depth만 남기도록한다.
당연하지만, depth는 던전의 수(dungeons.length)를 넘기면 안된다.

 

위의 고민을 토대로 코드를 작성해보자

 

class Solution {
    static int answer;
    static boolean visited[];
    
    public int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];

        dfs(0, k, dungeons);
        
        return answer;
    }
    
    void dfs(int depth, int k, int[][] dungeons) {
    
    	// 던전 수만큼 반복
        for(int i = 0; i < dungeons.length; i++) {
        
        	// 만약 k가 최소 요구 피로도 보다 크고, 방문한적이 없었다면,
            if(k >= dungeons[i][0] && !visited[i]) {
            
            	// 방문표시를 하고
                visited[i] = true;
                
                // 재귀적으로 호출
                dfs(depth + 1, k - dungeons[i][1], dungeons);
                
                // 방문표시를 해제한다. 예) 1 -> 1로 들어가서 조건을 만족하지 않으면 다시 1로 
돌아가게 만들어서 1 -> 2가 되게끔 처리
                visited[i] = false;
            }
           
            answer = Math.max(answer, depth);
        }
    }
}

 

많은 사람들이 이런식으로 dfs를 사용해서 풀었다. 아직 방문 처리에 대해 미숙한 부분이 있는것 같다.