[Coding Test] 프로그래머스 2단계 - 피로도

📚 문제 

 

✏️ 메모

 

1. 던전이 몇개가 있던지 간에, 모든 던전을 방문하는 경우의 수를 다 따져서 

2. 최대로 탐험할 수 있는 던전의 수를 파악해서 return 해주어야 함. 

3. 이때 초기 채력과 각 던전의 요구 체력, 체력 소모를 확인하여, 체력을 최대한 아껴 가장 많은 던전을 파악해야 함. 

💡 DFS

- 깊이 우선 탐색. 그래프 탐색 기법 중 하나 

- 루트 노트에서 시작해서 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방법

- 모든 노드를 방문하고자 하는 경우에 선택함

 

- 알고리즘을 구현할 때에는 어떤 노드를 방문했는지에 대한 여부를 반드시 확인해 주어야 한다. 

(검사하지 않을 경우 무한 루프에 빠질 수 있다.) 

- 재귀 함수와 스택 자료 구조를 이용하여 구현할 수 있다. 

(재귀함수 또한 후입 선출(LIFO) 의 성격을 갖는다 )

 

[Algorithm] DFS (깊이 우선 탐색)

 

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시

 

💡 Math.max()

public static int max(int a, int b) 

Java.lang.Math.max() 메서드

 

 

🔎 문제해결

class Solution {
    // 전역변수 선언
    private static int max = 0;
    public int solution(int k, int[][] dungeons) {
        // 각 던전 방문에 대한 boolean 값을 담을 배열 이므로 크기는 던전 배열의 Length
        boolean[] visited = new boolean[dungeons.length];
        // 던전 탐험 시작 시 초기화.
        // 탐색할 배열, 방문 유무 확인 배열, 현재 피로도 k, 탐험한 던전 수 count 를 매개변수로 주어야 함.
        dfs(dungeons, visited, k, 0);
        return max;
    }
    
    private static void dfs (int[][]dungeons, boolean[] visited, int k, int count) {
        // 최대 탐험 던전 수 계산
        max = Math.max(max , count);

        for(int i = 0; i < dungeons.length; i ++ ) {
            // 방문하지 않았고(visited 가 false ) 피로도(k)가 
            // 해당 던전의 최소필요 피로도(dungeons[i][0]) 보다 크면 방문.
            if (!visited[i] && dungeons[i][0] <= k ) {
                visited[i] = true;
                // 체력을 깍고 방문한 던전 수 증가 시킨 뒤에, 그 다음 던전 방문.
                dfs(dungeons, visited, k - dungeons[i][1], count + 1);
                // 방문을 다 했으면, 백트랙킹
                visited[i] = false;
            }
        }
    }
    
}

 

- 전역변수 선언, static 선언에 대한 궁금증이 생겼다.. 예전에 공부했던 걸 다 까먹은 듯. 보충이 필요함.