<Hard> Dungeon Games (LeetCode : C#)

https://leetcode.com/problems/dungeon-game/

📕 문제 설명

공주가 mxn 던전의 오른쪽 하단에 갇혔을 때 상단 왼쪽에 위치한 기사가 위치해있다. 던전에 나타나 있는 각 수치는 기사의 hp에 영향을 준다. 이때 기사가 공주를 구하러 가기 위해 가질 수 있는 최소한의 hp 반환하기
(기사의 체력은 0이 되면 바로 죽는 것으로 간주한다. 즉, 최소 시작 hp는 1이다.)

(기사는 오른쪽과 아래로만 움직일 수 있다.)

• Input
  던전 정보 (int[][])
• Output
  기사가 가질 수 있는 최소한의 hp (int)

예제

시도 1.

BFS로 모든 케이스 보기
=> 현재 값 기준 최소 체력, 현재 pos까지 왔을 떄의 체력 상태를 저장해서 진행

=> out of memory

public class Solution {
    public int CalculateMinimumHP(int[][] dungeon) {
        if (dungeon.Length == 1 && dungeon[0].Length == 1)
        {
            if (dungeon[0][0] < 0) return -(dungeon[0][0]) + 1;
            return 1;
        }

        int[] dirX = {0, 1};
        int[] dirY = {1, 0};
        int answer = -(Int32.MaxValue - 1);

        // 3x2
        // [m] [n] -> 행 : m , 열 : n
        // 현재 위치, 최소 체력, 현재 가는 길에 대한 체력 상태
        Queue<(int[], int, int)> queue = new Queue<(int[], int, int)>();
        queue.Enqueue((new int[2] {0, 0}, dungeon[0][0], dungeon[0][0]));

        while (queue.Count >= 1)
        {
            (int[], int, int) currInfo = queue.Dequeue();
            int[] currPos = currInfo.Item1;
            int minHp = currInfo.Item2;
            int currHp = currInfo.Item3;

            if (currPos[0] == dungeon.Length - 1 && currPos[1] == dungeon[0].Length - 1)
            {
                answer = Math.Max(answer, minHp);
                if (answer > 0) return 1;
                continue;
            }

            for (int i = 0; i < 2; i++)
            {
                int x = currPos[0] + dirX[i];
                int y = currPos[1] + dirY[i];

                if (x >= dungeon.Length || y >= dungeon[0].Length) continue;
                queue.Enqueue((new int[2] {x, y}, Math.Min(minHp, currHp + dungeon[x][y]), currHp + dungeon[x][y]));
            }
        }

        return -answer + 1;
    }
}

시도 1-1.

위에게 queue를 써가지고 out of memory 난 것 같아서 DFS로 변경했더니 시간 초과남 (다른 접근 필요)

public class Solution {
    int answer;
    int[] dirX;
    int[] dirY;
    int[][] dungeonInfo;
    public int CalculateMinimumHP(int[][] dungeon) {
        dungeonInfo = dungeon;
        if (dungeon.Length == 1 && dungeon[0].Length == 1)
        {
            if (dungeon[0][0] < 0) return -(dungeon[0][0]) + 1;
            return 1;
        }
        
        answer = Int32.MinValue;
        dirX = new int[2] {0, 1};
        dirY = new int[2] {1, 0};

        DFS(new int[2] {0, 0}, dungeon[0][0], dungeon[0][0]);
        if (answer == 1) return 1;
        return -answer + 1;
    }

    public void DFS(int[] currPos, int minHp, int currHp)
    {
        if (answer == 1) return;
        if (currPos[0] == dungeonInfo.Length - 1 && currPos[1] == dungeonInfo[0].Length - 1)
        {
            answer = Math.Max(answer, minHp);
            if (answer > 0) answer = 1;
            return;
        }

        for (int i = 0; i < 2; i++)
        {
            int x = currPos[0] + dirX[i];
            int y = currPos[1] + dirY[i];
            if (x >= dungeonInfo.Length || y >= dungeonInfo[0].Length) continue;
            DFS(new int[2] {x, y}, Math.Min(minHp, currHp + dungeonInfo[x][y]), currHp + dungeonInfo[x][y]);
        }
    }
}

시도 2.

우선 순위 큐 사용
=> 현재 요구하는 hp 가장 작은 애를 우선순위로 두고 우선 순위큐에 넣어 뽑기 (여기서 공주 있는 마지막 위치 도달하면 바로 끝내도록)

public class Solution {
    public int CalculateMinimumHP(int[][] dungeon) {
        if (dungeon.Length == 1 && dungeon[0].Length == 1)
        {
            if (dungeon[0][0] < 0) return -(dungeon[0][0]) + 1;
            return 1;
        }

        int[] dirX = {0, 1};
        int[] dirY = {1, 0};
        int answer = Int32.MinValue;

        // 우선 순위 : 현재까지 왔을 떄 필요한 hp가 제일 작은 애 
        // (position, currHp), 우선순위 : 최소한의 hp
        PriorityQueue<(int[], int), int> queue = new PriorityQueue<(int[], int), int>();
        queue.Enqueue((new int[2] {0, 0}, -dungeon[0][0]), -dungeon[0][0]);

        while (queue.TryDequeue(out (int[], int) currInfo, out int minHp))
        {      
            int[] currPos = currInfo.Item1;
            int currHp = currInfo.Item2;
            // 공주 위치 도달 시 반환 
            if (currPos[0] == dungeon.Length - 1 && currPos[1] == dungeon[0].Length - 1)
            {
                answer = Math.Max(answer, minHp) + 1;
                if (answer <= 0) return 1;
                return answer;
            }

            for (int i = 0; i < 2; i++)
            {
                int x = currPos[0] + dirX[i];
                int y = currPos[1] + dirY[i];

                if (x >= dungeon.Length || y >= dungeon[0].Length) continue;
                queue.Enqueue((new int[2] {x, y}, currHp - dungeon[x][y]), Math.Max(minHp, currHp - dungeon[x][y]));
            }
        }

        return -answer + 1;
    }
}

풀이

dp 사용한 풀이
핵심은 도착해야하는 지점부터 봐야한다는 것과 현재 요구하는 체력이 계산 상 음수가 되면 (즉 이미 충분하면) 1로 초기화 해야 한다는 것 (첫 시작에 음수 값들이 나오다가 양수를 만나서 현재 hp가 1로도 충분한 경우 생각하면 됨, 따라서 도착점에서 출발해서 양의 hp 만나다가 1로 충분해지는 경우 1로 초기화 하는 것)

Top - Down (Memoization)

public class Solution {
    public int CalculateMinimumHP(int[][] dungeon) {
        int n = dungeon.Length;
        int m = dungeon[0].Length;
        var dp = new int[n, m];
        return RequiredHealth(0, 0);

        int RequiredHealth(int i, int j) 
        {
            if (i >= n || j >= m) return Int32.MaxValue;
            // 마지막 지점 required health (양수면 1로 초기화, 음수면 현재 요구 + 1로 초기화)
            if (i == n - 1 && j == m - 1) return Math.Max(1 - dungeon[i][j], 1); 
            if (dp[i, j] != 0) return dp[i, j]; // 이미 기록되어 있으면 return

            int down = RequiredHealth(i + 1, j); 
            int right = RequiredHealth(i, j + 1);
            int result = Math.Max(Math.Min(down, right) - dungeon[i][j], 1); // 현재 기준 밑이랑 오른쪽 중 더 작은 값
            dp[i, j] = result;
            return result;
        }
    }
}

Bottom - up

public class Solution {
    public int CalculateMinimumHP(int[][] dungeon) {
        int n = dungeon.Length;
        int m = dungeon[0].Length;
        int x = 0;
        int y = 0;

        dungeon[n - 1][m - 1] = Math.Max(1 - dungeon[n - 1][m - 1], 1);

        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = m - 1; j >= 0; j--)
            {
                if (i + 1 < n) x = dungeon[i + 1][j];
                else  x = int.MaxValue;

                if (j + 1 < m) y = dungeon[i][j + 1];
                else y = int.MaxValue;

                if (x != int.MaxValue || y != int.MaxValue) dungeon[i][j] = Math.Max(Math.Min(x, y) - dungeon[i][j], 1);
            }
        }

        return dungeon[0][0];
    }
}

결과

(시간 복잡도 자체 차이 크지 않다)