1219. Path with Maximum Gold

https://leetcode.com/problems/path-with-maximum-gold

Path with Maximum Gold - LeetCode

백트래킹 문제

 

경로를 리스트로 쓰는 경우보다 집합으로 쓰는것이 훨씬 편함.

grid를 가져가서 방문했다고 맵에 체크하는 것보다 인덱스를 가지고 집합에 저장해두면 훨씬 수월하다.

 

 

 

class Solution(object):
    
    def getMaximumGold(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        self.max_value = 0
    
        def recur(r,c, visited, grid, total):
            
            visited.add((r,c))
            
            total += grid[r][c]
            
            for (x,y) in ((r+1,c), (r-1,c), (r,c+1), (r,c-1)):
                
                if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] != 0 and (x,y) not in visited:
                    
                    recur(x,y, visited, grid, total)
                    visited.remove((x,y))                                        
                else:
                    
                    self.max_value = max(self.max_value, total)

        for i in range(0, len(grid), 1):
            
            for j in range(0, len(grid[0]), 1):
                
                if grid[i][j] != 0:
                
                    recur(i,j,set(),grid,0)                   

        return self.max_value