피로도

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며,
일정 피로도를 사용해서 던전을 탐험할 수 있습니다.
이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와
던전 탐험을 마쳤을 때 소모되는 소모 피로도가 있습니다.
최소 필요 피로도는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며,
소모 피로도는 던전을 탐험한 후 소모되는 피로도를 나타냅니다.
예를 들어 최소 필요 피로도가 80, 소모 피로도가 20인 던전을 탐험하기 위해서는
유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러 개 있는데,
한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다.
유저의 현재 피로도 k와 각 던전별 최소 필요 피로도, 소모 피로도담긴
2차원 배열 dungeons가 매개변수로 주어질 때,
유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

풀이

public class DungeonExplorationOptimizer
{
    private static int _maxExploreCount = 0;
    private static int _dungeonLength = 0;
    private static Dungeon[]  _dungeons;

    public static int Solution(int k, int[,] dungeons)
    {
        _dungeonLength = dungeons.GetLength(0);
        _dungeons = new Dungeon[_dungeonLength];
        for (int i = 0; i < dungeons.GetLength(0); i++)
        {
            _dungeons[i] = new Dungeon(dungeons[i, 0], dungeons[i, 1]);
        }
        
        ExploreDungeon(k,0);
        
        return _maxExploreCount;
    }

    private static void ExploreDungeon(int currentFatigue, int exploreCount)
    {
        if(exploreCount > _maxExploreCount)
        {
            _maxExploreCount = exploreCount;
        }
        
        for (int i = 0; i < _dungeonLength; i++)
        {
            Dungeon d = _dungeons[i];
            
            if (!d.IsVisited && currentFatigue >= d.RequiredFatigue)
            {
                d.IsVisited = true; 
                
                ExploreDungeon(currentFatigue - d.ConsumedFatigue, exploreCount + 1);
                
                d.IsVisited = false; 
            }
        }
    }
}

class Dungeon
{
    public readonly int RequiredFatigue;
    public readonly int ConsumedFatigue;
    public bool IsVisited = false;

    public Dungeon(int requiredFatigue, int consumedFatigue)
    {
        RequiredFatigue = requiredFatigue;
        ConsumedFatigue = consumedFatigue;
    }
}

Dungeon 클래스

class Dungeon
{
    public readonly int RequiredFatigue;
    public readonly int ConsumedFatigue;
    public bool IsVisited = false;

    public Dungeon(int requiredFatigue, int consumedFatigue)
    {
        RequiredFatigue = requiredFatigue;
        ConsumedFatigue = consumedFatigue;
    }
}

• 2차원 배열로 주어진 던전에 관한 정보를 관리하고 향후 DFS 탐색시 방문 여부를 확인할 수 있도록 Dungeon클래스를 구성

초기 접근 방법

최소 필요 피로도와 소모 피로도 값을 통해 특정 우선순위를 결정해 답을 찾을 수 있을지 고민했으나 해당 변수를 통해 적절한 순서를 계산하기는 어려우며 조건에서 던전의 개수가 8개로 제한된 점을 고려해 전체를 탐색해 그 중 가장 큰 탐색 값을 찾는 방식을 사용
→ DFS 방식 중 하나인 백트래킹을 통해 전체 배열을 탐색해 답을 찾기로 결정

백트래킹 탐색

    private static void ExploreDungeon(int currentFatigue, int exploreCount)
    {
        if(exploreCount > _maxExploreCount)
        {
            _maxExploreCount = exploreCount;
        }
        
        for (int i = 0; i < _dungeonLength; i++)
        {
            Dungeon d = _dungeons[i];
            
            if (!d.IsVisited && currentFatigue >= d.RequiredFatigue)
            {
                d.IsVisited = true; 
                
                ExploreDungeon(currentFatigue - d.ConsumedFatigue, exploreCount + 1);
                
                d.IsVisited = false; 
            }
        }
    }

• 현재 탐색하는 횟수가 최대 탐색 횟수보다 클 때 최대 탐색 횟수 값을 업데이트
• 깊이 우선 방식을 활용해 전체 던전 배열을 탐색
• 방문되지 않은 노드를 방문하면서 요구 피로도를 충족하는 경우에 분기
• 해당 가지에서 탐색을 이어가다 끝까지 탐색을 마치면 방문을 취소