[87946] 피로도

✔ 피로도

[프로그래머스 87946]

문제 분석하기

DFS를 이용해 재귀호출하면서 완전탐색하도록 함

예) 던전1, 던전2, 던전3

던전1 → 던전2 → 던전 : 던전 1 방문 처리 → 던전2 호출 후, 던전1 방문 처리 초기화 ...

던전1 → 던전3 → 던전2 : 던전 1 방문 처리 → 던전3 호출 후, 던전1 방문 처리 초기화 ...

던전2 → 던전1 → 던전3

던전2 → 던전3 → 던전1

던전3 → 던전1 → 던전2

던전3 → 던전2 → 던전1

손으로 풀어보기

1. 방문 배열 선언
2. DFS로 완전탐색
   • 방문한 던전의 경우 true로 방문 처리 후 DFS
   • 다른 완전탐색에서는 방문하지 않은 것이 되어야 하므로 DFS 호출 후 false로 방문 초기화 
3. 완전탐색을 하며 가장 많이 방문할 경우를 반환 

슈도코드 작성하기

k(현재 피로도)
dungeons(최소 필요 피로도와 소모 피로도가 담긴 2차원 배열)
visited(방문 유무 배열)
dfs(0, k, dungeons)
answer 반환

dfs {
    for(i -> dungeons의 크기만큼) {
        if(방문하지 않은 던전이면서 최소 필요 피로도가 현재 피로도보다 작거나 같을 때) {
            visited[i] 방문 처리
            dfs(depth + 1, k - dungeons[i][1], dungeons)
            visited[i] 방문 초기화
        }
    }
    answer = Math.max(answer, depth)
}

코드 구현하기

/**
 * 87946) 피로도
 */
public class K005_87946 {
    static boolean[] visited;
    static int answer;

    // k(현재 피로도)
    // dungeons(최소 필요 피로도와 소모 피로도가 담긴 2차원 배열)
    public int solution(int k, int[][] dungeons) {
        answer = -1;
        // visited(방문 유무 배열)
        visited = new boolean[dungeons.length];
        // dfs(0, k, dungeons)
        dfs(0, k, dungeons);
        // answer 반환
        return answer;
    }

    // dfs
    private void dfs(int depth, int k, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            // 방문하지 않은 던전이면서 최소 필요 피로도가 현재 피로도보다 작거나 같을 때
            if (!visited[i] && dungeons[i][0] <= k) {
                // visited[i] 방문 처리
                visited[i] = true;
                // dfs(depth + 1, k - dungeons[i][1], dungeons)
                dfs(depth + 1, k - dungeons[i][1], dungeons);
                // visited[i] 방문 초기화
                visited[i] = false;
            }
        }
        // 최대 던전 수로 갱신
        answer = Math.max(answer, depth);
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K005_87946 solution = new K005_87946();

        int k = 80;
        int[][] dungeons = { { 80, 20 }, { 50, 40 }, { 30, 10 } };
        int result = solution.solution(k, dungeons);

        System.out.println(result);
    }
}