C# 피로도 - DFS 순열 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/87946

 

 

나의 풀이

public int solution(int k, int[,] dungeons) {

    int answer = 0;

    int size = dungeons.GetLength(0); 
    int[] arr = Enumerable.Range(0, size).ToArray();
    var permList = new List<int[]>();

    Perm(arr, 0, size, size, permList);

    for(int i = 0; i < permList.Count; i++)
    {
        int fatigue = k;
        int completeDungeon = 0;
        int[] indexArray = permList[i];

        for(int j = 0; j < size; j++)
        {
            int dungeonIndex = indexArray[j];
            if(fatigue < dungeons[dungeonIndex, 0])
                break;

            fatigue -= dungeons[dungeonIndex, 1];
            completeDungeon++;
        }

        if(answer < completeDungeon)
            answer = completeDungeon;
    }

    return answer;
}

private static void Perm(int[] arr, int depth, int n, int k, List<int[]> result)
{
    if(depth == k) // 끝. 출력
    {
        result.Add(arr.Clone() as int[]);
        return;
    }

    for(int i = depth; i < n; i++)
    {
        Swap(arr, i, depth);
        Perm(arr, depth + 1, n, k, result);
        Swap(arr, i, depth);
    }
}

private static void Swap(int[] arr, int i, int j)
{
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
}

순열을 구한다음, 하나씩 따져보면 되는 문제.

서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다.

 

순열을 구하는 기본 아이디어는 재귀를 통해 depth의 위치와 각 위치의 숫자를 스왑한다음, 

재귀로 호출하고 다시 원래대로 돌린다.

다시 원래위치로 돌리기 때문에 원본 array는 별도로 클론해주지 않아도 된다.

주의할 점은 depth와 i가 같을 때에도 예외처리하지않는다. (원래위치도 순열 중 하나이다)

 

이 과정이 끝나게 되면 depth와 k(구하려는 길이)가 같은 시점에서는 완성된 순열로서 재귀를 탈출하면 된다.