[LeetCode] 1219. Path with Maximum Gold

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

leetcode - Path with Maximum Gold

문제 유형 : dfs, 백트래킹, 행렬, 재귀

문제 난이도 : Medium

 

문제

In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:

• Every time you are located in a cell you will collect all the gold in that cell.
• From your position, you can walk one step to the left, right, up, or down.
• You can't visit the same cell more than once.
• Never visit a cell with 0 gold.
• You can start and stop collecting gold from any position in the grid that has some gold.

 

m x n의 크기의 행렬의 금광이 있는데, 숫자만큼 금이 있습니다.

당신은 어디서 시작해도 됩니다.

당신의 위치에서, 당신은 상하좌우로 이동가능합니다. 당신은 같은 셀을 다시는 갈 수 없습니다.

금이 없는 칸(0)에는 갈 수 없습니다.

당신은 어느 위치에서든 채광을 그만둘 수 있습니다.

 

풀이

이 문제는 dfs + 백트래킹으로 해결가능하다.

 

dfs() {

    visited[x][y] = true

    for(int i = 0; i < 4; i++) {

        // 상하좌우로 재귀 호출...

    }

    visited[x][y] = false

}

와 같은 형식으로 간편히 해결할 수 있다.

너무 티피컬한 문제이기 때문에, 자세한 풀이는 생략한다.

 

코드

C++

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

class Solution {
private:
    int maxGold;
    int m;
    int n;
public:
    void dfs(int sum, int row, int col, vector<vector<bool>>& visited, vector<vector<int>>& grid) {
        sum += grid[row][col];
        maxGold = max(maxGold, sum);
        visited[row][col] = true;
        for(int i = 0; i < 4; i++) {
            int nr = dr[i] + row;
            int nc = dc[i] + col;

            if(nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if(visited[nr][nc]) continue;
            if(!grid[nr][nc]) continue;
            dfs(sum, nr, nc, visited, grid);
        }

        visited[row][col] = false;
    }

    int getMaximumGold(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        maxGold = 0;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j]) {
                    dfs(0, i, j, visited, grid);
                }
            }
        }

        return maxGold;
    }
};