[TIL] 프로그래머스 - 피로도 문제 풀이 (Java, DFS)

 > 지난 주에 배운 내용을 토대로 주말 동안 아이템 시뮬레이터 과제 작업을 진행하고, 작업 전 후로 코딩 테스트 문제를 조금 풀었다. 그 중 마지막으로 푼 '피로도' 문제의 풀이를 적어보았다.

 

학습 키워드: Java, DFS

 

87946 - 피로도

1) 문제 설명 (원문은 링크 참고):

프로그래머스

 문제 요약: 게임 속 피로도 시스템을 모방한 문제로, dungeons 2차원 배열의 각 항목에 담긴 1차원 배열이 던전의 정보이며, 각 던전 정보는 [최소 필요 피로도, 소모 피로도] 의 두 가지 element로 구성되어 있다. 최소 필요 피로도는 진입에 필요한 요구량으로, 요구량 미만의 피로도를 가진 경우 진입이 불가능하다. 요구량이 충족되는 경우 현재 피로도 k에서 소모 피로도 만큼을 소모하여 던전에 진입할 수 있다. 최대한 많은 종류의 던전을 방문하는 경우의 방문 수를 구하는 문제다.

 

 조건: 1 <= k <= 5000, 1 <= 소모 피로도 <= 최소 필요 피로도 <= 1000, 던전 피로도 수치 중복 있음

 

 

2) 제출 코드:

class Solution {
    private int[][] dungeons;
    private int max = 0;
    
    public int solution(int k, int[][] dungeons) {
        this.dungeons = dungeons;
        boolean[] visited = new boolean[dungeons.length];
        
        for (int i = 0; i < dungeons.length; i++) {
            visited[i] = true;
            enterTheDungeon(k, 0, i, visited);
            visited[i] = false;
        }
        
        return max;
    }
    
    private void enterTheDungeon(int k, int depth, int dungeon, boolean[] visited) {
        if (k < dungeons[dungeon][0]){
            if (max < depth) max = depth;
            return;
        }
        k -= dungeons[dungeon][1];
        depth++;
        
        for (int i = 0; i < visited.length; i++) {
            if (visited[i]) continue;
            visited[i] = true;
            enterTheDungeon(k, depth, i, visited);
            visited[i] = false;
        }
        
        
        if (max < depth) max = depth;
    }
}

 DFS(Depth-First-Search)로 푸는 문제인데, visited[i]의 값을 false로 되돌리지 않는 바람에 시간을 많이 쓰게됐다. 기본적으로 각각의 노드에서 인접한 노드를 방문하는 것을 recursion 형식으로 구성하는데, 이전에 방문한 노드를 또 방문해서는 안되기 때문에 boolean 배열 visited를 생성하여 이동 전후로 visited 상태를 변경해주는 작업을 해준다. 실제로 노드로 연결되어 있지는 않기 때문에 배열을 순회하면서 이미 방문한(visited[i] == true) 노드는 continue로 넘어가줘야 한다.

 

 recursion으로 다음 던전을 방문할 때 마다 최소 피로도 요구치를 충족하는지 확인해주고, 충족하지 않는다면 return, 충족한다면 소모 피로도 만큼을 k에서 빼준다. return을 하는 시점에서 최대 깊이와 현재 깊이를 비교하여 큰 값으로 max를 갱신해주면 최대 몇 군데의 던전을 방문할 수 있는지를 알 수 있다.

 

 

3) 수정한 코드:

 처음에 코드를 좀 난잡하게 작성하는 바람에 중복되는 부분이 생겨서 모양이 조금 이상해졌는데, 루프 부분을 합치고 불필요한 계산을 줄여 아래와 같이 다듬어 주면 가독성도 높아지고 동작 시간 또한 약간 절약할 수 있다.

class Solution {
    private int[][] dungeons;
    private int max = 0;
    
    public int solution(int k, int[][] dungeons) {
        this.dungeons = dungeons;
        boolean[] visited = new boolean[dungeons.length];
        enterTheDungeon(k, 0, visited);
        return max;
    }
    
    private void enterTheDungeon(int k, int depth, boolean[] visited) {
        for (int i = 0; i < visited.length; i++) {
            if (visited[i] || k < dungeons[i][0]) continue;
            visited[i] = true;
            enterTheDungeon(k - dungeons[i][1], depth + 1, visited);
            visited[i] = false;
        }
        
        if (max < depth) max = depth;
    }
}

 기존 코드는 가장 바깥에 해당하는 루프가 밖으로 분리되어 있어서 if문을 루프 밖에 적었으나, 둘을 합치게 되면 첫 루프의 피로도 체크를 위해서 if문을 루프 안으로 넣어줘야 한다. 또한 파라미터의 dungeon 번호는 enterTheDungeon 함수의 루프 속에 if를 옮기게 되면서 던전 번호인 루프의 index i를 참조할 수 있기 때문에 더 이상 인자로 받을 필요가 없어진다.

 

4) 결과:

 성능 요약: 메모리: 98.6 MB, 시간: 0.08 ms