[2024] Day26. 576. Out of Boundary Paths

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 26일 (금)
Leetcode daily problem

576. Out of Boundary Paths

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

Problem

정수 m과 n의 크기를 가진 그리드에서 시작점에서 출발하여 경로를 따라 움직이다가 경계를 벗어나는 경우의 수를 계산하는 문제이다.
여기서의 경로는 상하좌우로만 이동할 수 있으며, 한 번의 이동은 한 칸씩의 이동이다.

Solution

dynamic programming

각 칸마다 해당 칸에 도달할 수 있는 경로의 수를 저장하면서, 경로가 격자의 경계를 벗어나는 경우의 수를 계산

Code

MOD_VAL = 1e9 + 7

class Solution:
    def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:
        total = 0
        locations = {(i, j): 1}
        for i in range(N):
            new_locations = {}
            for location, ways in locations.items():
                for delta in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    new_location = (location[0] + delta[0], location[1] + delta[1])
                    if self._out_of_bound(new_location, m, n):
                        total = (total + ways) % MOD_VAL
                    else:
                        if new_location not in new_locations:
                            new_locations[new_location] = 0
                        new_locations[new_location] += ways % MOD_VAL
            locations = new_locations
        return int(total)
    
    def _out_of_bound(self, location, m, n):
        return not(0 <= location[0] < m and 0 <= location[1] < n)

Complexicity

시간 복잡도

공간 복잡도

---