[Lv.2] 피로도 : Java

프로그래머스

 

 

 

 

이해하기

처음 시도했던 방식은 다음과 같다.

1. 모든 경우의 수 탐색 : 순열 사용
2. 던전 입장 가능 여부 확인
3. 피로도 계산

import java.util.*;

class Solution {
    List<int[]> list = new ArrayList<>();

    public int solution(int k, int[][] dungeons) {
        int[] order = {0, 1, 2};

        permutation(order, 0, order.length, order.length);

        int count = 0;
        int max = 0;
        for (int i = 0; i < list.size(); i++) {
            int pirodo = k;
            count = 0;
            int[] cur = list.get(i);
            for (int j = 0; j < cur.length; j++) {
                int idx = cur[j];
                if (pirodo >= dungeons[idx][0]) {
                    pirodo -= dungeons[idx][1];
                    count++;
                }
            }
            max = Math.max(max, count);

            if (max == dungeons.length) {
                return max;
            }
        }

        return max;
    }

    public void permutation(int[] order, int depth, int n, int r) {
        if (depth == r) {
            int[] temp = order.clone();
            list.add(temp);
            return;
        }

        for (int i = depth; i < n; i++) {
            swap(order, depth, i);
            permutation(order, depth + 1, n, r);
            swap(order, depth, i);
        }
    }

    public void swap(int[] order, int depth, int i) {
        int temp = order[depth];
        order[depth] = order[i];
        order[i] = temp;
    }
}

 

순열은 풀 때마다 어렵게만 느껴졌는데 아래 블로그를 참고해서 응용해보았다.

순열 Permutation (Java)

 

그렇지만 줄줄이 뜨는 실패...^^

시간초과도 아니고 그냥 실패라고만 떠서 뭐가 문제였는지 파악은 하지 못했다.

테스트 케이스는 통과한 것으로 보아 뭔가 로직이 꼬인 것 같은데🥹

 

 

도저히 모르겠어서 아래 블로그를 참고하였다.

[프로그래머스] 피로도 - JAVA [자바]

이 문제는 백트래킹 dfs 문제였다네...

 

접근 방법은 다음과 같다.

1. 이미 방문한 던전인지 확인
   • visited 배열 이용
   • 만약 visited = true라면 다음으로 넘어감
2. 각 던전의 필요 피로도와 현재 피로도를 비교하며 탐험 여부 판단
   • 방문한 적 없고, 현재 피로도 <= 필요 피로도라면 점화식 수행
     1. 해당 던전을 방문한 것으로 처리
     2. depth + 1과 현재 피로도에서 해당 던전의 소모 피로도만큼 감소한 상태로 다음 재귀
     3. 해당 던전을 방문하지 않은 것으로 처리 (백트래킹 때문?)

이 문제는 완전 탐색이기 때문에 점화식의 종료 조건은 따로 없다.

 

문제풀이

class Solution {
    static boolean[] visited;
    static int count = 0;

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

    public void dfs(int depth, int fatigue, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            if (visited[i] || dungeons[i][0] > fatigue) {
                continue;
            }

            visited[i] = true;
            dfs(depth + 1, fatigue - dungeons[i][1], dungeons);
            visited[i] = false;
        }
        count = Math.max(count, depth);
    }
}

 

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

 

파라미터를 줄이기 위해 전역 변수로 visited 배열과 count를 선언한다.

 

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

 

visited 배열을 dungeon 배열에 맞게 만들어주고, dfs를 돌린다.

 

    public void dfs(int depth, int fatigue, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            if (visited[i] || dungeons[i][0] > fatigue) {
                continue;
            }

 

던전을 순회하며, 만약 이미 방문했거나 필요 피로도가 현재 피로도보다 크다면 방문하지 못하고 넘어간다.

 

            visited[i] = true;
            dfs(depth + 1, fatigue - dungeons[i][1], dungeons);
            visited[i] = false;
        }

 

방문 가능하다면 visited[i]를 true로 변경해주고, 1 늘어난 depth와 줄어든 피로도로 다시 dfs를 돌린다.

백트래킹을 위해 visited[i]는 다시 false로 변경해준다.

 

        count = Math.max(count, depth);

 

count는 Math.max로 계산한다.

 

 

 

생각보다 풀이는 쉬웠지만 역시 구현은 어렵다...ㅜㅅㅜ

bfs는 감 좀 잡았다고 생각했는데, dfs는 더 공부해야겠다.