[LeetCode] 576. Out of Boundary Paths

https://leetcode.com/problems/out-of-boundary-paths/description/?envType=daily-question&envId=2024-01-26

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Out of Boundary Paths

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.

Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 10^9 + 7.

 

m x n의 그리드와 공이 있다.

공은 [startRow, startColumn]에 있다.

당신은 현재 위치에서 상하좌우로 인접한 곳으로 이동할 수 있다.

이를 maxMove번 할 수 있다.

 

정수 m,n,maxMove,startRow, startColumn이 주어진다. 공이 영역 밖을 나가는 모든 경우의 수를 구하시오.

값이 커질 수 있으니, 1e9+7로 나눈 나머지를 반환하시오.

 

 

풀이

dp+dfs, 또는 2차원배열 dp로 풀 수 있다.

dp+dfs만 다루도록 하겠다.

 

dp[row][col][남은이동] = 현재 위치+ 남은 이동수일때의 경우의 수로 한다.

row, col이 범위를 벗어나면 경우의 수 1반환,

이동을 다 소진하면 0을 반환한다.

dp값이 있다면, 반환한다.

 

상하좌우로 인접한 위치로 이동하면서 하위 경우의 수들을 누적하면서 dp에 저장한다.

 

 

코드

C++

class Solution {
    const int MOD = 1e9+7;
    const vector<int> dr = {-1, 1, 0, 0};
    const vector<int> dc = {0, 0, -1, 1};
    int dp[51][51][51];
    int maxRow, maxCol;
public:
    int solve(int row, int col, int move) {
        if(row < 0 || row >= maxRow || col < 0 || col >= maxCol) {
            return 1;
        }
        if(move <= 0) return 0;
        if(dp[row][col][move] != -1) return dp[row][col][move];

        long long res = 0;
        for(int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = col + dc[i];
            res = (res + solve(nr, nc, move-1))%MOD;
        }
        return dp[row][col][move] = res%MOD;
    }

    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        maxRow = m;
        maxCol = n;
        memset(dp, -1, sizeof(dp));

        return solve(startRow, startColumn, maxMove);
    }
};