通学路(DP)


質問元:https://programmers.co.kr/learn/courses/30/lessons/42898
質問する

  • 持続的な豪雨が一部の地域を水没させた.水没していない地域を通って学校に行きたいです.家から学校までの道はm×nサイズのグリッドで表すことができます.

  • 下図はm=4,n=3である.


  • 最左上隅(すなわち家屋の所在地の座標)は(1,1)であり、最右下角(すなわち学校の所在地の座標)は(m,n)である.

  • グリッドサイズm、n、および水没領域座標を含む2 Dフラットピットにパラメータ化します.右側と下側だけに移動し、家から学校までの最短パスの数を1000000 7で割ってからソリューション関数に戻ってください.
  • せいげんじょうけん
    * 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
       - m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
    * 물에 잠긴 지역은 0개 이상 10개 이하입니다.
    * 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
    class Solution {
        public int solution(int m, int n, int[][] puddles) {
            int answer = 0;
    
            int[][] map = new int[n + 1][m + 1]; // 1-base index
            /**
             * 시작 -> 1, 1(1행 1열)
             * 끝 -> m, n(n행 m열)
             */
    
            int[][] directions = {
                    { -1, 0 }, // 윗쪽
                    { 0, -1 }, // 왼쪽
            };
    
            if (puddles[0].length > 0) {
                for (int i = 0, size = puddles.length; i < size; i++) {
                    int x = puddles[i][0];
                    int y = puddles[i][1];
    
                    map[y][x] = -1; // 웅덩이
                }
            }
    
            map[1][1] = 1;
    
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (map[i][j] != 0) continue;
    
                    int[] temp = new int[2]; // 0번 -> 위쪽, 1번 -> 왼쪽
    
                    for (int k = 0; k < 2; k++) {
                        int dy = i + directions[k][0];
                        int dx = j + directions[k][1];
    
                        // 탐색 가능한 범위인 경우
                        if (dy > 0 && dy <= n && dx > 0 && dx <= m) {
                            temp[k] = map[dy][dx];
                        }
                    }
                    
                    if (temp[0] == 0 || temp[1] == 0) {
                        map[i][j] = Math.max(temp[0], temp[1]) % 1000000007;
                    } else if (temp[0] == -1 || temp[1] == -1) {
                        map[i][j] = Math.max(Math.max(temp[0], temp[1]), 0) % 1000000007;
                    } else  map[i][j] = (temp[0] + temp[1]) % 1000000007;
                }
            }
    
            answer = map[n][m] % 1000000007;
            
            return answer;
        }
    }
  • 論理ができたらエリアに挿入する.
  • 移動方向は右下に固定されており、どこへ行っても最短経路が確保されている.
  • dfsで解くとタイムアウトになる可能性があるのでDPで解きました.
  • 主な論理は、各位置において自分の左上隅の値を表示し、この2つの値の和を自分の値とする.この値は、現在位置までの回数を意味します.
  • この場合、2つの値のうちの1つも0と-1の場合の処理に注意する.いずれかの値が0の場合、2つの値のうちより大きな値で割り当てられます.
  • 両値のいずれか1の場合、両数のうちより大きい値とし、両値とも負数であれば0とする.
  • 配列の最後の要素値が正しい.
  • 効率テストの最終実行%1億007は、まだ完全には理解できませんが、すべての値で実行する必要があります.