93. 피로도

 

기본 틀 :

 

using System;

public class Solution {
    public int solution(int k, int[,] dungeons) {
        int answer = -1;
        return answer;
    }
}

 

위의 문제를 재귀함수를 이용한 DFS가 아닌 방법으로 풀어보고자 시도했지만

 

너무 많은 자료구조와 반복문을 요구하게 돼. 결국, DFS로 문제를 풀게 됐다.

 

재귀함수를 이용한 DFS를 사용하지 않을려고 한 이유는 

 

내 자신이 재귀함수를 잘 사용하지 못 하는 상태에서 DFS나 BFS를 구현하는데 

 

많은 어려움을 겪고 있기 때문이다.

 

하지만, 이번 기회를 바탕으로 DFS와 BFS를 재귀함수를 이용해서 풀어보며 익숙해지고자 한다.

 

 

 

처음 재귀함수에 제공돼야 할 변수가 뭐가 있을지 고민해보았다.

 

그 결과,

 

던전 방문횟수(count), 남은 피로도(k), 던전(dungeons), 방문 여부(visited)

 

가 필요하다고 판단 됐다.

 

그리고, 반환형을 고려해봤을 때 반환형은 존재하지 않는 것이 좋다고 판단했다.

(반환형과 DFS를 잘 연결하는 것을 여려워 함...)

(ex, return count + DFS(~~~~~))

 

그럴 경우, 결과를 저장할 그릇?이 필요하게 되는데 전역 List를 사용하게 됐다.

 

 

using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public List<int> answer = new List<int>();
    
    // 필요한 매개 변수
    
    // 현재 방문 횟수
    // 현재 피로도
    // 던전
    // 방문 여부
    public void DFS(int count, int k, int[,] dungeons, bool[] visited)
    {
        // 모든 던전을 방문 못 할 수도 있기 때문에 여기에 두기
        answer.Add(count);
        
        // 탐색 및 방문 가능 여부 조회
        for(int i = 0; i < dungeons.GetLength(0); i++)
        {
            if(!visited[i] && k >= dungeons[i, 0])
            {
                visited[i] = true;
                DFS(count + 1, k - dungeons[i,1], dungeons, visited);
                // 다른 DFS에서 동작하기 위해 방문 여부 false로 변경
                // 어차피 함수의 매개변수로 visited를 넘겨줬기 때문에 방문 여부 제공됨
                visited[i] = false;
            }
        }
    }

    
    public int solution(int k, int[,] dungeons) {
        bool[] visited = new bool[dungeons.GetLength(0)];
        
        DFS(0, k, dungeons, visited);
        
        return answer.Max();
    }
}

 

위의 코드를 보면 DFS 함수가 실행될 때, answer.Add(count)를 하는 이유는

 

피로도에 의해 던전을 돌 수 없는 상황을 고려해서 반복문과 조건문 밖에 배치시켰다.

 

반복문에서는 방문 여부와 피로도를 바탕으로 던전 방문 여부를 판단하고

 

해당 던전의 방문 여부 visited[index]를 true로 바꿔줬다.

 

그리고, 다시 DFS에 필요한 매개 변수들을 넣어줬다.

 

이때, DFS밑에 visited[i] = false로 바꿔준 이유는 for문의 index가 변경된 이후

 

즉, 순서가 다른 형식으로 던전을 탐색할 수도 있기 때문이다.

(이거 안 해줘서 테스트 케이스 통과 못 하고 있었다...)

 

이렇게 DFS를 종료한 후 answer에서 가장 큰 수가 결과가 되기 때문에

 

 answer.Max()로 결과를 가져왔다.