[Today's Algorithm] 프로그래머스 - 피로도 (Java / 완전탐색)

문제 : 프로그래머스 Level 2 (피로도)
사용 알고리즘: 완전탐색 (DFS + 백트래킹)

 

---

오늘은 프로그래머스의 피로도 문제를 풀었다. 제한된 피로도 안에서 최대한 많은 던전을 돌아야 하는 최적화 문제다.

원래는 조건만 보고 풀려고 했는데 순서의 중요성을 깨닫고 완전탐색을 써야겠다고 생각하게 된 문제였다.

1. 완전탐색을 선택하게 된 과정

- 처음 했던 고민:
처음에는 소모 피로도가 가장 적은 던전이나 최소 필요 피로도가 낮은 던전 순으로 정렬하여 탐색하는 Greedy 알고리즘을 떠올렸다. 하지만 이 문제는 어떤 순서로 던전을 진입하느냐에 따라 이후에 열리는 선택지가 완전히 달라진다. 그렇기 때문에 부분적인 최적의 경로가 전체 최적의 경로를 보장하지 못한다는 것을 알 수 있었다.

- 완전탐색(DFS) 선택 이유:

다행히 이 문제는 던전 개수가 최대 8개밖에 되지 않는다. 가능한 모든 순서를 다 따져봐도 경우의 수가 약 4만 개 정도다. 컴퓨터는 1초에 억 단위의 일을 처리할 수 있으므로 모든 경우의 수를 싹 다 뒤져보는 완전탐색(DFS)을 써도 시간 안에 충분히 안전하게 통과할 수 있다고 판단했다.

2. 틀렸던 이유와 트러블 슈팅 과정
방문 기록을 초기화하지 않아서 생겼던 문제:
처음 코드를 돌렸을 때 자꾸 이상한 값이 나왔다. 디버깅을 해보니까 한쪽 길을 다 탐험하고 나서 다른 길을 탐험하러 갈 때 이전에 방문했던 흔적(isVisit)이 그대로 남아있는 것이 원인이었다.

해결방법

-  다른 길을 갈 때는 이전 기록을 지워줘야겠다라고 생각해서, 탐색이 끝난 뒤 돌아올 때 isVisit[i] = false로 방문 상태를 원래대로 돌려놓는 백트래킹 코드를 추가했다. 이 덕분에 모든 경우의 수를 정확하게 탐색할 수 있었다.

 

import java.util.*;

class Solution {
    int maxDungeonCount = -1;
    boolean[] isVisit;
    
    public int solution(int k, int[][] dungeons) {
        isVisit = new boolean[dungeons.length];
        finding(k, dungeons, 0);
        return maxDungeonCount;
    }
    
    private void finding(int k, int[][] dungeons, int dungeonCount) {
        for (int i = 0; i < dungeons.length; i++) {
            // 최소 필요 피로도를 만족해야함, 방문하지 않은 던전이어야 함
            if (k >= dungeons[i][0] && isVisit[i] == false) {
                // 1. 방문하면 true로 바꿔줘야함 
                isVisit[i] = true;
                // 2. 재귀함수 호출
                finding(k-dungeons[i][1], dungeons, dungeonCount + 1);
                // 3. 재귀함수를 호출하고 나면 새로운 경로를 시작해야하기 때문에 초기화시켜야함
                isVisit[i] = false;
            }
        }
        maxDungeonCount = Math.max(dungeonCount, maxDungeonCount);
        // 방문한 경우 maxDungeonCount를 세야함
    }
}