Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 금광 그리드 최대 골드 수집 경로 문제

m × n 크기의 금광 그리드가 있다고 가정해 봅시다. 이 광산의 각 칸에는 그 칸에 들어 있는 금의 양을 나타내는 정수가 저장되어 있으며, 값이 0이면 빈 칸을 의미합니다. 우리의 목표는 다음 조건을 지키면서 수집할 수 있는 최대 금의 양을 구하는 것입니다.

문제 조건

  • 칸에 도착할 때마다 해당 칸에 있는 모든 금을 수집합니다.
  • 현재 위치에서 한 번에 한 칸씩 왼쪽, 오른쪽, 위, 아래로만 이동할 수 있습니다.
  • 같은 칸을 두 번 이상 방문할 수 없습니다.
  • 금이 0인 칸은 절대 방문하지 않습니다.

예를 들어 입력이 [[0,6,0],[5,8,7],[0,9,0]]이라면 결과는 24입니다. 최대 금을 얻을 수 있는 경로는 9 → 8 → 7이며, 이 경로를 따라 얻는 금의 합이 24이기 때문입니다.

접근 방법: DFS + 백트래킹

이 문제는 모든 시작 지점에서 탐색을 시도해야 하므로 깊이 우선 탐색(DFS)과 백트래킹을 활용하는 것이 가장 자연스러운 해법입니다. 핵심 아이디어는 다음과 같습니다.

  • 금이 있는 모든 칸을 시작점으로 삼아 DFS를 수행합니다.
  • 방문한 칸은 임시로 -1로 표시하여 재방문을 막습니다.
  • 탐색이 끝나면 원래 값으로 되돌려(백트래킹) 다른 경로 탐색에 영향을 주지 않도록 합니다.
  • 네 방향으로 이동하며 얻을 수 있는 금의 최댓값을 누적합니다.

알고리즘 단계

dfs(grid, n, m, i, j) 함수는 다음과 같이 동작합니다.

  1. i >= n, j >= m, i < 0, j < 0 중 하나라도 참이거나, grid[i][j]가 -1(방문함) 또는 0(빈 칸)이면 0을 반환합니다.
  2. temp = grid[i][j], cost = grid[i][j]로 저장한 뒤 grid[i][j] = -1로 방문 표시를 합니다.
  3. cost에 상하좌우 네 방향 DFS 호출 결과 중 최댓값을 더합니다.
  4. grid[i][j] = temp로 값을 복원하고 cost를 반환합니다.

메인 함수(getMaximumGold)는 다음 순서로 진행됩니다.

  1. n은 행의 개수, m은 열의 개수, ans는 0으로 초기화합니다.
  2. 모든 칸을 순회하면서 값이 0이 아닌 칸에서 DFS를 호출하고, 그 결과로 ans를 갱신합니다.
  3. 순회가 끝나면 ans를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int dfs(vector<vector<int>>& grid, int n, int m, int i, int j){
        if(i>=n || j>=m ||i<0||j<0 || grid[i][j]==-1 || grid[i][j] == 0)return 0;
        int temp =grid[i][j];
        int cost = grid[i][j];
        grid[i][j] = -1;
        cost+=max({dfs(grid,n,m,i+1,j),dfs(grid,n,m,i-1,j),dfs(grid,n,m,i,j+1),dfs(grid,n,m,i,j-1)});
        grid[i][j] = temp;
        return cost;
    }
    int getMaximumGold(vector<vector<int>>& grid) {
        int n = grid.size() ;
        int m = grid[0].size();
        int ans = 0;
        for(int i =0;i<n;i++){
            for(int j =0;j<m;j++){
                if(grid[i][j]){
                    ans = max(ans,dfs(grid,n,m,i,j));
                }
            }
        }
        return ans;
    }
};
main(){
    vector<vector<int>> v = {{0,6,0},{5,8,7},{0,9,0}};
    Solution ob;
    cout << (ob.getMaximumGold(v));
}

실행 결과

입력:

[[0,6,0],[5,8,7],[0,9,0]]

출력:

24

복잡도 분석

각 시작 칸마다 최대 세 방향(되돌아가는 방향 제외)으로 분기되며 경로를 완전 탐색하므로, 시간 복잡도는 최악의 경우 지수적으로 증가합니다. 다만 실제 코딩 테스트 환경에서는 그리드 크기가 작게 제한되는 경우가 많아(예: 리트코드 기준 최대 15×15) 이 방식으로 충분히 통과할 수 있습니다. 공간 복잡도는 재귀 호출 스택 깊이에 비례하여 O(m × n)입니다.