피로도(프로그래머스-완전탐색)

문제

코드

class Solution {
    static int answer=0;
    public int solution(int k, int[][] dungeons) {
        for(int i=0;i<dungeons.length;i++){
            boolean[] visited=new boolean[dungeons.length];
            dfs(i,k,0,visited,dungeons);
        }
        return answer;
    }
    public void dfs(int start, int hp, int count, boolean[] visited, int[][] dungeons){
        visited=visited.clone();
        if(hp>=dungeons[start][0]&&visited[start]!=true){
            visited[start]=true;
            hp-=dungeons[start][1];
            count++;
            for(int i=0;i<visited.length;i++){
                if(visited[i%visited.length]==false)
                    dfs(i,hp,count,visited,dungeons);
            }
        }
        answer=Math.max(answer,count);
    }
}

풀이

(1) 처음에 시작할 던전을 차례대로 정해서 dfs() 메소드를 실행한다.
(2) dfs()에서는 방문할 던전에 입장할 수 있는지 확인하고, 던전에 입장이 가능하다면 count(입장한 던전 수)를 +1 해준다. 또한 hp(피로도)를 깎고, visited 리스트에도 입장한 던전을 체크 해준다.
(3) 다음 입장할 던전을 찾는다. (모든 던전을 순회하며, 방문하지 않은 던전이 있으면 그 던전을 시작점으로 하는 dfs() 메소드를 실행한다.)
(4) dfs() 메소드가 완료될 때, count와 answer을 비교하여, 더 높은 수를 answer로 만들어준다.

결과

전형적인 dfs 문제였다. 처음에는 던전을 입장하는 모든 경우의 수를 계산해야 해서 시간초과가 나지 않을까 걱정했는데, 다행히 조건에서 던전의 수가 그리 많지 않아 문제가 없었다. 딱 하나 아쉬운 점은 visited 리스트가 dfs() 함수 실행할때 마다 새로 생겨야 한다는 점이다. 나는 여기서 clone()함수로 매개변수로 받아온 visited을 복사해주었다. 만약 이렇게 하지 않고 하나의 visited을 사용하게 된다면, 다음과 같은 예가 생긴다.
1-2-3 순으로 던전을 방문한 경우가 있을 때, 1,2,3 모두 visited이 true로 표시되기 때문에 다른 경우의 수를 계산할 때는 들어가지 못한다. 그래서 각 경우의 수마다 새로운 visited이 필요했다. 더 효율적인 방법이 없을까 생각했지만, 이게 최선인것 같다.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges