LeetCode (C/C++, Java) 1219. Path with Maximum Gold

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

 

---

풀이

주어진 배열의 최대 사이즈가 15 * 15이므로 금이 있는 모든 구역을 탐색하며 최대로 얻을 수 있는 금의 양을 찾는다.

이 때 dfs로 탐색하며, 반환값을 [현재 구역의 금 양 + 탐색한 구역들에서 최대로 얻을 수 있는 금의 양] 으로 설정하여 탐색한 경로에서의 최대 양을 찾아 반환한다.

---

C/C++ 코드

class Solution {
public:
    int mv[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int getMaximumGold(vector<vector<int>>& grid) {
        int maxValue = 0;

        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j])
                    maxValue = max(maxValue, dfs(grid, i, j));
            }
        }
        return maxValue;
    }

    int dfs(vector<vector<int>>& grid, int r, int c) {
        int nowValue = grid[r][c], maxValue = 0;

        grid[r][c] = 0;
        for (int i = 0; i < 4; i++) {
            int nr = r + mv[i][0], nc = c + mv[i][1];
            if (nr < 0 || grid.size() <= nr || nc < 0 || grid[0].size() <= nc || !grid[nr][nc]) continue;
            maxValue = max(maxValue, dfs(grid, nr, nc));
        }
        grid[r][c] = nowValue;

        return nowValue + maxValue;
    }
};

 

Java 코드

class Solution {
    private int[][] mv = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int m, n;

    public int getMaximumGold(int[][] grid) {
        int maximum = 0;
        m = grid.length;
        n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) continue;
                maximum = Math.max(findMaxGoldPath(grid, i, j), maximum);
            }
        }
        return maximum;
    }

    private int findMaxGoldPath(int[][] grid, int r, int c) {
        int sum = 0, gold = grid[r][c];
        grid[r][c] = 0;

        for (int i = 0; i < 4; i++) {
            int nr = r + mv[i][0], nc = c + mv[i][1];
            if (nr < 0 || m <= nr || nc < 0 || n <= nc || grid[nr][nc] == 0) continue;
            sum = Math.max(findMaxGoldPath(grid, nr, nc), sum);
        }
        
        grid[r][c] = gold;
        return sum + grid[r][c];
    }
}