프로그래머스 - 피로도 (Java)

 

문제 개요

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러 개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할 수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"]입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

 

예제 입출력

피로도	던전 배열	출력 값
80	[[80,20],[50,40],[30,10]]	3

---

 

풀이

이번에도 스킬 체크에 도전하다가 이 문제와 직면했다.

문제를 처음 보자마자 완전탐색 알고리즘으로 풀 수도 있겠구나라는 생각을 했지만, 그래프 탐색 알고리즘이 잘 기억나지 않아서 그냥 그리디 알고리즘으로 풀려고 했었다.

 

내가 적용하려고 했던 방법은 최소 필요 피로도가 높은 던전부터 탐색하도록 하는 것이었다.

운이 좋게도 위에 예제 입출력을 넣었을 때는 정답인 3이 출력되었고, 그대로 그냥 제출하여 채점하기를 눌렀다.

 

역시는 역시였다. 정확성 테스트를 한 개도 통과하지 못했다.

그래서 하는 수 없이 dfs를 활용해서 풀기로 다짐했다.

 

나는 dfs를 구현할 때 주로 재귀를 사용하는데, dfs를 사용하는 게 오랜만이라 능숙히 코드를 작성하지 못했던 것 같다. 결과적으로 다른 사람의 코드를 보고 힌트를 얻어 코드를 완성할 수 있었다. (근데 아직은 왜 bfs로 하면 안 되는지에 대해 정확히 이해하진 못한 상태다. 현재는 단순히 dfs가 더 구현하기 편해서 dfs를 사용했다.)

 

---

 

코드

cclass Solution {
    public int solution(int k, int[][] dungeons) {
        boolean[] visited = new boolean[dungeons.length];
        int answer = dfs(visited, k, dungeons, 0);
        return answer;
    }
    
    public int dfs(boolean[] visited, int k, int[][] dungeons, int depth) {
        int max = depth;
        for (int i=0 ; i<dungeons.length ; i++) {
            if (visited[i] || k<dungeons[i][0])
                continue;
            visited[i] = true;
            int buf = dfs(visited, k - dungeons[i][1], dungeons, depth+1);
            if (buf > max)
                max = buf;
            visited[i] = false;
        }
        return max;
    }
}

 

코드 리뷰

1. 방문했는지 여부를 저장할 배열인 visited를 선언한다.
2. dfs로직이 돌아갈 재귀함수를 실행하여 그 결과를 answer에 넣고 리턴하여 종료시킨다.
3. dfs()는 방문 여부가 담긴 배열, 현재 피로도, 던전 피로도 배열, 깊이를 매개변수로 받게 작성했다.
4. depth가 가장 큰 경우를 구하기 위해 max에 초기 값으로 depth를 저장한다. 
5. 전체 던전 중 갈 수 있는 던전을 조사하기 위해 for루프를 작성했다.
6. 방문했거나 최소 필요 피로도가 현재 피로도보다 높은 던전이면 탐색할 수 없도록 continue처리를 했다.
7. 6번의 조건에 부합하지 않아서 새로 탐색할 수 있는 던전이 나오면 visited[]에 해당 인덱스를 true로 만든다.
8. for문 안에서 int형 변수 buf에 dfs()를 실행한 결과를 담았다.
   • 결과적으로 dfs에서 출력하고자 하는 것은 그래프의 각가지를 탐색해서 가장 깊은 가지의 depth이다.
   • 따라서 buf에 dfs()의 실행 후 출력 값을 저장하는 것은 그래프에서 현재 가지의 이후에 나올 수 있는 모든 경우의 수 중 가장 깊은 depth를 가졌던 가지의 depth를 buf에 저장하는 것과 같다.
9. 받아온 값을 buf에 넣고 max와 비교해서 max보다 크면 max에 buf를 저장한다.
   • max는 처음에 현재 depth를 담아서 초기화 됐었다.
10. 현재 조사하던 곳의 visited[]를 false로 만든다.
    • false로 만드는 이유는 visited가 배열이기 때문에 dfs()를 수행하다가 해당 메소드 안에서 새로운 dfs()를 실행하기 위해 visited를 파라미터로 넣어줬다고 해도 하나의 배열이기 때문에, 만약 그래프를 탐색하다가 하나의 가지를 모두 조사했는데 전체 노드(장소, 스팟 등 갈 수 있는 곳을 지칭)를 방문했었다면 visited의 모든 값이 true가 된다.
    • 전체 가지를 조사한 것이 아니라 하나의 가지를 조사했을 뿐인데 모든 곳을 방문한 것이 되어 다른 가지를 조사할 수 없는 상황이 되어버리기 때문에 dfs()를 수행한 뒤에 false로 만들어주어 다른 가지를 탐색할 수 있게 해 주기 위함이다.
    • 예를 들어 depth가 0인 최초 상태에서 1번 노드를 시작으로 dfs탐색을 시작한 경우에 찾을 수 있는 최대 depth와, 동일하게 depth가 0인 최초 상태에서 2번 노드를 시작으로 dfs 탐색을 시작했을 때 찾을 수 있는 최대 depth가 다를 수 있다.
    • for문을 돌면서 1번 노드로 시작해서 모든 경우의 수를 구한 다음에 visited[0]을(배열의 인덱스는 0부터 시작) false로 만들었기 때문에 2번 노드로 시작해서 모든 경우의 수를 구할 수 있게 해 줄 수 있는 것이다.
11. for문이 종료되면 max를 리턴해준다.
    • dfs의 시작이든, 중간이든, 끝자락이든 for문이 종료되었다는 것은 그래프에서 해당 가지를 모두 탐색했다는 뜻이기 때문에 max를 리턴해주면 된다.

 

---

 

제출 결과

 

처음에는 머릿속에 정리가 잘 되지 않았을 때는 다른 사람들의 코드를 보고 이해하면서 그대로 만들었다.

나는 dfs()를 실행한 결과로 최대 depth를 가져오는 방법을 택했지만, 다른 풀이로는 answer와 visited를 전역변수로 놓고 dfs() 를 실행했을 때 그래프 탐색을 하다가 가지의 끝에 도달했다면, 전역변수 answer를 가장 깊은 depth로 설정하는 식의 방법으로 해결한 사람들도 있었다.

 

나는 문제를 처음 직면하고 dfs()를 실행한 결과로 int형의 최대 depth를 리턴하게 하고 싶었으나, 잘 안돼서 위 방법으로 이해하고 넘어가려고 했다.

 

하지만 조금 더 고민해서 최대 depth를 리턴하게 만들어볼 수 있었다. 뭐가 더 생각하기 편하고 좋은지는 모르겠지만 최초 내 생각을 구현할 수 있어서 좋았고, 완전 탐색에 대해 더 공부해야겠다는 생각을 했다.