[알고리즘/Programmers] LV2. 피로도 (Java)

 

오늘의 학습 키워드

• DFS

오늘의 회고

1. 문제

문제 URL

프로그래머스

2. 해결 방안

/** 87946
 * 코딩테스트 연습 > 완전탐색 > 피로도
 */
public class test_87946_X {

    static boolean[] visited;
    static int count = 0;

    public static void main(String[] args) {
        int[][] dungeons = {{80,20},{50,40},{30,10}};
        System.out.println(solution(80, dungeons));
    }

    public static int solution(int k, int[][] dungeons) {
        visited = new boolean[dungeons.length];
        dfs(0, k, dungeons);
        return count;
    }

    public static void dfs(int depth, int k, int[][] dungeons) { // depth: 현재까지 방문한 회수
        for(int i=0; i< dungeons.length; i++) {
            if(visited[i] || dungeons[i][0] > k) {
                continue;
            }
            visited[i] = true;
            dfs(depth+1, k-dungeons[i][1], dungeons);
            visited[i] = false; // 백트래킹 기법. 앞선 재귀 끝나고 다른 경로에서는 방문할 수 있도록 초기화
        }
        count = Math.max(depth, count); // 최대 방문수 갱신
    }
}

• 가능한 모든 경우의수를 구해야하니 DFS 재귀를 통해 모든 경우를 탐색하여 푼다.
• visited : 방문한 노드를 표기한다. visited[i] = false; 로 초기화하는 이유는 앞선 재귀(=먼저 탐색 완료한 경로) 끝나고 다른 경로 방문할 때, 새로 방문 가능하도록 초기화 하는 것이다.
• count : 최대 방문 수를 기록한다. dfs 함수 마지막에 현재까지의 방문 회수인 depth 와 count를 비교하여 최대값으로 갱신한다.

3. 피드백

• DFS인데 BFS로 잘못 짚음. 아직 스스로 풀이 방법을 구분하는데 확실하지 않는 것 같다. 더 많이 접하고 풀어봐야 할듯.