[Lv.2] 피로도 [프로그래머스_코딩테스트] [Brute Force, 완전탐색, 순열] [30분]

🔍 문제 요약

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

프로그래머스

피로도 시스템이 있어서 k라는 현재 피로도가 있고 dungeons라는 [최소 필요 피로도, 사용되는 피로도]가 배열로 주어질 때 최대한 들어갈 수 있는 던전의 수를 구하는 문제

🧠 나의 접근 방식과 시행착오

문제의 접근 방식부터 해맨 상태라 못 푼 문제. 이 문제를 접근하면서 가장 중요하게 생각했던건 조건에 맞는 최소 피로도 중에 제일 큰 값이면서 소모 피로도가 제일 작은 것을 우선시해야 하지 않나란 생각이었다. 다만 이렇게 생각하니 일단 먼저 정렬을 시켜야 하지 않나란 생각부터 했었지만, 생각보다 그렇게 해서 다음에 어떻게 찾아나가야 하나가 문제가 되었다. 이 문제는 애초에 방향성을 완전탐색을 한다고 생각하고 BruteForce하게 접근했어야 하는데 잘 못 접근하였다. 

    public struct DungeonData
    {
        public int Min { get; set; }
        
        public int Need { get; set; }

        public DungeonData(int min, int need)
        {
            Min = min;
            Need = need;
        }
    }
    
    /// <summary>
    /// 피로도
    /// https://school.programmers.co.kr/learn/courses/30/lessons/87946
    /// </summary>
    public int solution(int k, int[,] dungeons)
    {
        int answer = 0;
        
        // 가지고 있는 현재 피로도 k
        // dungeons [최소 피로도, 소모 피로도]
        // 조건에 맞는 최소 피로도 중에 제일 크면서 소모 피로도가 제일 작은 것을 우선시해야 최고의 효율
        var dungeonList =  new List<DungeonData>();

        for (int i = 0; i < dungeons.GetLength(0); i++)
        {
            dungeonList.Add(new DungeonData(dungeons[i, 0], dungeons[i, 1]));
        }
        
        
        return answer;
    }

✅ 풀이 코드

해당 문제는 완전탐색을 하는 DFS, 백트래킹으로 푸는 방향으로 피드백을 주었다. 이 기회에 DFS(재귀)에 대해서 다시 한 번 학습을 제대로 해두기로 하자. visited로 이미 방문 한 곳을 전역으로 체크를 하는 형태이고, 결과를 구하기 위한 maxCount 역시 전역으로 계산을 하고 있음을 알 수 있다. DFS라는 함수로 재귀호출을 하고 있으며 호출 전에 visited에 체크를 하고 후에 false로 백트래킹을 하고 있다.

using System;

public class Solution
{
    int maxCount = 0;
    bool[] visited;

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

    void DFS(int depth, int k, int[,] dungeons, int n)
    {
        maxCount = Math.Max(maxCount, depth);

        for (int i = 0; i < n; i++)
        {
            if (visited[i]) continue;

            int min = dungeons[i, 0];
            int cost = dungeons[i, 1];

            if (k >= min)
            {
                visited[i] = true;
                DFS(depth + 1, k - cost, dungeons, n);
                visited[i] = false; // 백트래킹
            }
        }
    }
}

🔄 정리

모든 방법을 완전탐색을 해서 최대의 횟수를 구하는 문제로 DFS + 백트래킹 방식으로 접근하는 문제이다. 실제 라이브 서비스를 하면서 개발을 할 때 익숙치 않았던 DFS에 대해서 확실히 집고 넘어가는 기회가 되기로 하자