[TIL #13] 피로도

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

프로그래머스

 

던전이 있고 피로도가 있으면 던파 밖에 없지.

이거 문제 좀 재밌게 풀겠구만 싶었다.

지금은 최소 피로도는 8과 30밖에 없지만 그러면 문제의 의미가 없으니까...

다양한 최소 피로도와 소모 피로도가 문제엔 존재했다.

 

어쨌든 이 문제에선 모든 루트를 탐색해야 한다.

그럼 자연스럽게 가장 먼저 떠올리는 방법은 DFS가 될 것이다.

순열로도 불가능하지 않지만 "굳이?"라는 생각이 든다.

 

풀이는 이렇게 진행될 수 있다.

1. 방문하지 않았고 최소 피로도 만족하는지 확인
    - 안 하면 그냥 넘어감
2. 만족하면 방문을 ``true``로
3. 다음 방문으로 넘어감 (재귀 호출)
    - 여기서 다시 1로 돌아가게 된다
4. 현재 카운트와 기존 최대 카운트 비교 후 큰 값 저장
5. 방문을 ``false``로 하여 다른 경로 탐색 가능케 함

이걸 코드로 옮기면 다음과 같다.

function dfs(k, dungeons, visited, count) {
    let maxCount = count;

    for (let i = 0; i < dungeons.length; i++) {
        // 방문하지 않았고 최소 피로도 만족 확인
        if (!visited[i] && k >= dungeons[i][0]) {
            visited[i] = true;
            
            // 피로도 소모 후 다음 재귀로
            let currentCount = dfs(k - dungeons[i][1], dungeons, visited, count + 1);
            maxCount = Math.max(maxCount, currentCount);
            visited[i] = false;
        }
    }

    return maxCount;
}

코드가 심플하게 나와 좋다.

DFS의 장점이기도 하고.

 

사실 여기서 DFS를 선택할 수 있었던 이유는,

던전 개수가 최대 8개기 때문이다.

완전 탐색의 시간 복잡도는 $O(N!)$인데, 8이면 40320이다.

매우 빠르게 계산할 수 있다는 의미가 된다.

 

만약 던전 개수가 30이라면?

완전 탐색으로 10^30을 계산해야 하는데, 우주가 망하기 전까지 계산하지 못할 것이다.

이 경우엔 그리디나 휴리스틱을 통한 접근이 유효하게 될 것이다.

여하튼 던전 개수가 적고 DFS가 구현도 빠르고 코드도 간결하기 때문에 선택한 것이다.

 

여기서 BFS를 사용해도 공간 복잡도에 대해서만 손해를 보지,

시간 복잡도에선 유의미한 차이가 없을 것이다.

 

진짜 던파는 이렇게 고민할 일이 잘 없는데 말이지...

이렇게 해야 하면 끔찍할 것 같다.