피로도

피로도 문제 풀러가기

프로그래머스

 

해당 문제는 완전 탐색을 요구하는 문제이다.

 

문제에서는 피로도 라는 시스템이 있고 던전을 탐험하기 위해서는 최소 필요 피로도가 있으며, 던전을 탐험하고 나면 보유 피로도에서 소모피로도 만큼의 피도로가 까이게 된다.

 

이러한 방식 속에서 주어지는 던전들을 최대한 많이 도는 방법을 찾아야 하므로 DFS와 백트래킹을 이용하여 해당 문제를 풀어보기로 하였다.

 

가장 먼저 해주어야 할 것은 전역으로 사용가능한 값들을 선언하는 것이다.

static boolean[] visited; //방문 여부를 저장할 배열
static int maxDungeonCount = 0; //탐험한 던전의 수

반환해줘야할 탐험한 던전의 수와 DFS를 진행하며 방문 여부를 저장할 배열을 boolean타입으로 만들어 줘야 한다.

 

public static int solution(int k, int[][] dungeons){
    visited = new boolean[dungeons.length];  // 던전 개수 만큼의 방문 배열을 생성
    dfs(k, dungeons, 0); // DFS 탐색 시작  ->  k는 보유 피로도, dungeons는 던전, 0은 탐험수를 나타냄
    return maxDungeonCount;
}

k의 값은 나에게 주어지는 피로도 값, dungeons는 던전의 배열인데 각각 최소 필요 피로도와 소모 피로도 값을 가지고 있다.

각 던전별로 방문 여부를 저장하여야 하기에 dungeons의 크기에 해당하는 boolean타입 배열을 만들어 준다.

이후 dfs 메서드를 통하여 로직을 실행시켜주면 된다.

 

dfs의 로직은 다음과 같다.

 

public static void dfs(int k, int[][] dungeons, int count){
    // 현재까지 탐험한 던전의 수를 갱신
    maxDungeonCount = Math.max(maxDungeonCount, count);

    for(int i =0 ; i < dungeons.length ; i++){
        if(!visited[i] && k >= dungeons[i][0]){ // 방문하지 않고, 최소 필요 피로도 이상일때
            visited[i] = true;
            dfs(k-dungeons[i][1], dungeons, count+1); //피로도 소모 후 DFS 다시 호출
            visited[i] = false; // 백트래킹 (원상복구)
        }
    }
}

이를 처음 접하는 사람은 조금 어렵게 느껴질 수도 있다.

먼저 dfs에서 매개변수로 받아오는 값은 보유피로도, dungeons, count 이렇게 총 3개의 값을 받아온다.

여기서 count는 현재 진행한 던전의 수를 말한다.

dfs가 실행되면 가장 먼저 maxDungeonCount의 값을 count값과 비교하여 최대값인지 확인하고 갱신하는 작업을 한다.

 

이후 for문은 현재피로도로 탐험할 수 있는 모든 던전을 탐색하며 DFS를 수행하는 역할을 한다.

i=0부터 시작하기 때문에 모든 던전을 확인하고 

아직 방문하지 않은 던전이면서 현재 피로도가 최소 필요 피로도보다 높은경우 해당 던전을 방문처리 후 남은 피로도로  다시 dfs를 호출하여 탐색을 이어나가는 알고리즘이다. 해당 함수를 호출하여 더이상 탐색을 이어나가지 못하는 경우 다시 던전을 원상복구 하여 탐색 가능 상태로 만든다.

 

만약 모든 던전을 탐색하여 다음 더이상 탐험할 던전이 없는 경우 백트래킹을 통해 모든 던전이 다시 탐사 가능 상태로 돌아오게 하고 해당 메서드가 종료된다.

 

기본적으로 DFS와 백트래킹이라는 알고리즘을 알고 있어야 풀 수 있을것 같은 문제였다.

 

주말이 되면 DFS와 백트래킹에 대해서도 따로 정리하도록 하겠다.