1219. Path with Maximum Gold

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

 

Difficulty : Medium

 

Status : Solved

 

Time : ??:??:??

 

---

 

문제 설명

 

---

 

풀이

 

DFS로 풀이할 수 있는 문제. 총 grid 영역이 15 x 15이므로, 탐색을 통해 시간 내에 모든 경로를 테스트해 볼 수 있겠다.

 

풀이 코드 (Python)

class Solution:
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    visited = [[]]
    n = 0
    m = 0

    def dfs(self, grid: List[List[int]], x : int, y : int, golds : int) -> int :
        next_gold = 0
        for i in range(4) :
            ax, ay = x + self.dx[i], y + self.dy[i]
            if -1 < ax < self.n and -1 < ay < self.m and not self.visited[ay][ax] and grid[ay][ax] > 0 :
                self.visited[ay][ax] = True
                next_gold = max(next_gold, self.dfs(grid, ax, ay, grid[ay][ax]))
                self.visited[ay][ax] = False
        return golds + next_gold

    def getMaximumGold(self, grid: List[List[int]]) -> int:
        self.m = len(grid)
        self.n = len(grid[0])
        self.visited = [[False for _ in range(self.n)] for _ in range(self.m)]
        result = 0
        for i in range(self.m) :
            for j in range(self.n) :
                if grid[i][j] > 0 :
                    self.visited[i][j] = True
                    result = max(result, self.dfs(grid, j, i, grid[i][j]))
                    self.visited[i][j] = False
        return result

 

 

풀이 코드 (Go)

var (
    dx []int = []int{-1, 1, 0, 0}
    dy []int = []int{0, 0, -1, 1}
    visited [][]bool
    n int
    m int
)

func dfs(grid [][] int, x, y, golds int) int {
    next_gold := 0
    for i := 0; i < 4 ; i++ {
        ax := x + dx[i]
        ay := y + dy[i]
        if ay < 0 || ay >= m || ax < 0 || ax >= n {
            continue
        }
        if !visited[ay][ax] && grid[ay][ax] > 0 {
            visited[ay][ax] = true
            if result := dfs(grid, ax, ay, grid[ay][ax]); result > next_gold {
                next_gold = result
            }
            visited[ay][ax] = false
        }
    }
    return golds + next_gold
}


func getMaximumGold(grid [][]int) int {
    m = len(grid)
    n = len(grid[0])
    visited = make([][]bool, m)
    for i := 0; i < m; i++ {
        visited[i] = make([]bool, n)
    }
    result := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 0 {
                continue
            }
            visited[i][j] = true
            if tmp := dfs(grid, j, i, grid[i][j]); tmp > result {
                result = tmp
            }
            visited[i][j] = false
        }
    }
    return result
}