[medium] 576. Out of Boundary Paths

문제

https://leetcode.com/problems/out-of-boundary-paths/

Out of Boundary Paths - LeetCode

---

풀이방법

중복방문 허용하면서 maxMove 이내로 움직여서 공을 칸 밖으로 내보낼 수 있는 경우의 수를 구하는 문제이다

처음에는 DFS로 접근하면 될 줄 알았는데 중복방문이 되다보니 시간초과가 났다

값을 저장하면서 처리해야 시간초과가 해결될 것 같은데 구현하는 과정에서 헷갈려서 다른 사람의 풀이를 봤다

(row, col, 남은이동횟수) 일 때 가능한 경우의 수를 저장해나가면서 중복체크 하지 않도록 하는 방법이었다

반응형

---

코드

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        result = [0]
        direction = [[-1,0],[1,0],[0,-1],[0,1]]
        visit = {}
        
        def dfs(r,c,move):
            if move < 0:
                return 0
            if r<0 or r>=m or c<0 or c>=n:
                return 1

            if (r,c,move) in visit:
                return visit[(r,c,move)]
            
            tmp = 0
            for dr,dc in direction:
                newr = r+dr
                newc = c+dc
                tmp += dfs(newr,newc,move-1)
                visit[(r,c,move)] = tmp
            return tmp
                    
        result[0] = dfs(startRow,startColumn,maxMove)
        return result[0] % (10**9 + 7)