[2024] day 136. Leetcode 1219. Path with Maximum Gold

gunny·2024년 5월 14일

leetcode 1219. Path with Maximum Gold leetcode 1219. Path with Maximum Gold python

코딩테스트

목록 보기

450/530

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

2024년 5월 14일 (화)
Leetcode daily problem

1219. Path with Maximum Gold

https://leetcode.com/problems/path-with-maximum-gold/?envType=daily-question&envId=2024-05-14

Problem

m x n 크기의 금광 격자에서 이 광산의 각 셀은 해당 셀의 금 양을 나타내는 정수를 가지며, 비어 있으면 0이다.

다음 조건에 따라 수집할 수 있는 최대 골드 금액을 반환한다.

셀에 위치할 때마다 해당 셀에 있는 모든 금을 수집함
현재 위치에서 왼쪽, 오른쪽, 위, 아래로 움직일 수 있음
동일한 셀을 두 번 이상 방문할 수 없음
금이 0인 셀은 방문할 수 없음
금이 있는 그리드의 어느 위치에서나 금 수집을 시작하고 중지할 수 있음

Solution

dfs (깊이 우선 탐색)

2차원 그리드에서 금광을 탐험하여 얻을 수 있는 최대 금의 양을 찾는 문제이다. 주어진 그리드는 행(row)과 열(column)로 이루어져 있으며, 각 셀은 금의 양을 나타낸다. 시작점에서 출발하여 상하좌우로 이동할 수 있으며, 한 번 방문한 셀은 다시 방문할 수 없다.
이때, 금을 얻을 수 있는 경로 중에서 가장 많은 금을 얻을 수 있는 경로의 금의 양을 반환해야 하는데 전형적인 DFS로 풀 수 있는 문제이다.

주어진 그리드에서 0을 방문할 수 없으므로, 0 이아닌 그리드를 모두 방문하면서, 이동할 수 있는 상하좌우로 움직여서 그리드 안의 셀의 금의 값을 더하고 최대값을 업데이트 해간다.

방문했던 셀을 다시 재방문하지 않기 위해서 방문한 셀을 저장하는 집합(set)을 계속 업데이트 한다.

최종적으로 업데이트된 금의 합을 반환한다.

Code

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        visited = set()
        
        def dfs(x,y):
            if x<0 or x>=ROWS or y<0 or y>=COLS or grid[x][y]==0 or (x,y) in visited:
                return 0
            
            visited.add((x,y))
            maxGold = 0
            
            for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
                next_x, next_y = x+dx, y+dy
                maxGold = max(maxGold, dfs(next_x, next_y))
                
            visited.remove((x,y))
            
            return grid[x][y] + maxGold
                
        
        
        ans = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c]!=0:
                    ans = max(ans, dfs(r,c))
                    
        return ans