프로그래머스 스쿨(Java - Lv.2) - 피로도[경우의수를 따지는 완전탐색]

문제

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

프로그래머스

 

 

풀이

class Solution {
    boolean[] visited;
    int cnt = 0;
    int[][] dungeons;
    int answer = 0;
    public int solution(int k, int[][] dungeons) {
        this.visited = new boolean[8];
        this.dungeons = dungeons;
        for(int i=0;i<dungeons.length;i++){
            dfs(i,visited,k);
        }
        return answer;
    }
    
    public void dfs(int p,boolean[] visited,int fatigue){
        //피로도가 부족할 경우 최대값비교
        if(fatigue<dungeons[p][0]){
            if(cnt>answer) answer = cnt;
            return;
        }
        //방문 처리 및 피로도 소모, 깊이 1증가
        cnt++;
        visited[p] = true;
        fatigue -= dungeons[p][1];
        //깊이가 최대일 경우 최대값비교
        if(cnt==dungeons.length){
            if(cnt>answer) answer = cnt;
            //이전 노드로 돌아가기위해 원복
            visited[p] = false;
            fatigue += dungeons[p][1];
            cnt--;
            return;
        }
        
        //재귀
        for(int i=0;i<dungeons.length;i++){
            if(!visited[i]){
                dfs(i,visited,fatigue);
            }
        }
        //이전 노드로 돌아가기위해 원복
        visited[p] = false;
        fatigue += dungeons[p][1];
        cnt--;
    }
}

 

해설

1. 완전탐색을 하려면 dfs를 사용해야하는 것은 어렵지 않게 파악 할 수 있었다.

또한 경우의수는 최대개수가 8개이므로 8!의 경우 컴퓨터의 연산으로 보아 충분히 가능한 경우의수라 판단함.

그러나 지금까지는 완전탐색시 노드의 개수가 한정되어있어 어렵지 않게 그다음 이동할 위치를 지정할 수 있었으나

이번엔 남은 숫자들을 모두 탐색해야하기에 boolean 배열을 이용하여 그 배열에서 visited가 true가 아닐 경우

순회하도록 하였다.

 

2. 조건 달성시 return 처리까지 옳게 하였으나

깊이가 최대일 경우 그 조건을 원복시키지않고 return 하지 않아 테스트케이스에서 에러를 보게되어 그를 찾는데 시간이 일정 소모되게 되었다. node의 경우 어떤식으로 처리해야할지 알게되어 지금까지의 문제와 비슷하나 색다른 방식이었다.