[프로그래머스 C#] Lv.2 피로도

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

조건에 따라 현재 피로도로 가장 많은 던전을 구하는 경우의 클리어 던전 횟수를 반환하는 문제

- 입장 조건 최소 피로도로 인해 변수가 많아 모든 경우의 수를 구해야 함

 -> DFS 알고리즘을 이용해 모든 경우의 수를 구함

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

 

풀이 과정

using System;

public class Solution
{
    public int solution(int k, int[,] dungeons)
    {
        int answer = 0; // 최대로 클리어 할 수 있는 던전 개수
        var boolArray = new bool[dungeons.GetLength(0)]; // 방문 배열
        
        DFS(dungeons, k, boolArray, 0, ref answer); // 완전탐색
        return answer;
    }
    
    public void DFS(int[,] dungeons, int k, bool[] boolArray, int clearCount, ref int answer)
    {
        for(int i = 0; i < dungeons.GetLength(0); i++)
        {
            // 이미 클리어 했거나 클리어 할 수 없는 던전이라면
            if(boolArray[i] || k < dungeons[i, 0])
                continue;
            
            boolArray[i] = true;
            DFS(dungeons, k - dungeons[i, 1], boolArray, clearCount + 1, ref answer);
            boolArray[i] = false;
        }
        
        answer = Math.Max(answer, clearCount);
    }
}