[자바] 프로그래머스 - 피로도 / 공포의 백트래킹 알고리즘 정복하기

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

프로그래머스

프로그래머스 정답률 55%, Level2 난이도의 백트래킹 문제입니다.

 

---

문제 간단 분석 

이 문제를 간단하게 분석해보자면 다음과 같습니다.

먼저 던전을 탐험하려면 나의 피로도가 '최소 필요 피로도' 만큼 있어야하고, 거기서 던전을 탐험하면 '소모 피로도'를 감소시킵니다.

매개변수로 들어오는 dungeons는 2차원 배열이고 요소 하나는 다음과 같습니다. {최소 필요 피도로, 소모 피로도}

 

이제 더 쉽게 예시를 들어서 설명 드리겠습니다.

[현재 나의 피로도 k = 80] 여기서 [50, 40] 이라는 던전을 탐험할 수 있을까요?

필요 피로도만큼 존재하니 이 던전을 탐험하게 되면 [현재 나의 피로도 k = 40]이 됩니다.

현재 남은 피로도에서 [80,20]의 던전을 탐험할 수 없습니다. 왜냐면 소모 피로도는 있지만, 최소 필요 피로도가 부족하기 때문입니다.

 

최대로 돌 수 있는 던전을 구하는게 목적이므로, 우리는 모든 던전을 조합으로 구성하여 최대로 돌 때 몇 번 갈 수 있는지 카운팅 해주면 됩니다.

즉 던전 A, B, C 가 존재한다면 // A-B-C, A-C-B, B-A-C, B-C-A, C-A-B, C-B-A 이렇게 모든 경우를 탐색해주면 됩니다.

 

 

 

풀이 방법 도출하기

우리는 이제 문제를 분석했으니 문제를 풀어야합니다.

이 문제를 풀기 위해서 '모든 경우'를 탐색해야합니다. 던전의 모든 순서를 조합하여 정답을 구해야 하므로 우리는 여기서 백트래킹을 이용해서 풀어야함을 알 수 있습니다.

 

그렇다면 문제를 푸는 순서는 다음과 같습니다.

1. 백트래킹을 이용해서 모든 경우를 구한다.

2. 모든 경우를 구하는 순간 answer = Math.max(answer, depth); 로 정답을 초기화 시켜준다. (여기서 depth는 던전을 몇 번 탐색했는지를 가르키는 변수입니다.)

3. 출력한다.

 

 

정답 코드

class Solution {
    public static int answer;
    public static boolean[] visited;

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

    public static void backTracking(int depth, int k, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            if (k >= dungeons[i][0] && !visited[i]) {
                visited[i] = true;
                backTracking(depth + 1, k - dungeons[i][1], dungeons);
                visited[i] = false;
            }
        }
        answer = Math.max(answer, depth);
    }
}

 

 

 

백트래킹 쉽게 이해하기

    public static void backTracking(int depth, int k, int[][] dungeons) {
        for (int i = 0; i < dungeons.length; i++) {
            if (k >= dungeons[i][0] && !visited[i]) {
                visited[i] = true;
                backTracking(depth + 1, k - dungeons[i][1], dungeons);
                visited[i] = false;
            }
        }
        answer = Math.max(answer, depth);
    }

 

위에 코드는 백트래킹 알고리즘을 이용해서 모든 조합을 구해주는 코드입니다.

 

1. if문에서는 방문하지 않은 던전이고, 최소 필요 소모도가 현재 피로도보다 낮은 경우 if문 내부 로직을 실행하게 됩니다.

if문을 타게 되면 던전을 방문한 것으로 가정하므로, visited는 true로 만들어줍니다.

 

2. 그리고 다음 백트래킹을 타게 됩니다. 이 때, depth는 +1 을 해줍니다. (depth는 방문한 던전의 개수가 됩니다. 초기 백트래킹 접근할 때 depth 값은 0입니다.) 또한 피로도는 던전의 피로도만큼 차감시키고 태워줍니다.

 

3. 만약에 어느 순간 더이상 if 내부 백트래킹을 탈 수 없다면 다시 1번으로 돌아옵니다. (이때 1번에서 진행한 백트래킹타는 로직은 종료)

그리고 visited[i] = false 로 만들어주는데, 이 이유가 중요합니다.

visited[i] = false가 되는 이유는, 다음 번에 또 사용할 수 있기 때문입니다.

 

즉 던전 A,B,C 가 있다면 A-B-C, A-C-B 를 탐색했다면 이제 B를 선두로 탐색을 할텐데, 이때 A의 visited를 false로 해줘야지 B에서도 B-A-C, B-C-A 이런식으로 사용할 수 있기 때문입니다.