1219. Path with Maximum Gold / TypeScript

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.

 

Example 1:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

Example 2:

Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

 

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

 

풀이

function getMaximumGold(grid: number[][]): number {
  const m = grid.length
  const n = grid[0].length
  const visited = Array.from({ length: m }, () =>
    Array.from({ length: n }).fill(false)
  )
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ]

  const dfs = (i, j) => {
    if (grid[i][j] === 0) {
      return 0
    }
    let sum = grid[i][j]
    visited[i][j] = true
    for (const [dx, dy] of directions) {
      const newX = i + dx
      const newY = j + dy
      if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
        if (!visited[newX][newY]) {
          sum = Math.max(sum, grid[i][j] + dfs(newX, newY))
        }
      }
    }
    visited[i][j] = false
    return sum
  }

  let ans = 0
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      ans = Math.max(ans, dfs(i, j))
    }
  }
  return ans
}

 

DFS(깊이 우선 탐색)를 사용하여 2D 격자(grid)에서 가능한 최대 골드를 찾는 문제를 해결

 

• 변수 초기화:
  • m: 격자의 행(row) 수를 저장
  • n: 격자의 열(column) 수를 저장
  • visited: 각 격자의 방문 여부를 추적하는 2D 배열로, 초기에는 모든 값을 false로 설정
  • directions: 네 방향(동, 서, 남, 북)을 나타내는 배열
• DFS 함수:
  • dfs(i, j): 현재 위치 (i, j)에서 시작하여 가능한 최대 골드를 찾는 재귀 함수
  • if (grid[i][j] === 0): 현재 위치에 골드가 없는 경우, 0을 반환.
  • let sum = grid[i][j]: 현재 위치의 골드 양을 sum에 저장.
  • visited[i][j] = true: 현재 위치를 방문했다고 표시합니다.
  • for (const [dx, dy] of directions): 네 방향 각각에 대해 반복.
    • const newX = i + dx;: 새로운 X 좌표를 계산
    • const newY = j + dy;: 새로운 Y 좌표를 계산
    • if (newX >= 0 && newX < m && newY >= 0 && newY < n): 새로운 위치가 격자 범위 내에 있는지 확인
    • if (!visited[newX][newY]): 새로운 위치가 아직 방문되지 않은 경우,
      • sum = Math.max(sum, grid[i][j] + dfs(newX, newY)): 현재 위치의 골드와 새로운 위치에서의 DFS 결과를 더한 값을 최대 골드와 비교하여 갱신
  • visited[i][j] = false: 탐색이 끝난 후 현재 위치를 방문하지 않은 상태로 되돌림
  • return sum: 현재 위치에서 가능한 최대 골드를 반환
• 메인 로직:
  • let ans = 0: 최대 골드를 저장할 변수를 초기화
  • for (let i = 0; i < m; i++): 각 행에 대해 반복
  • for (let j = 0; j < n; j++): 각 열에 대해 반복
    • ans = Math.max(ans, dfs(i, j)): 현재 위치에서 DFS를 시작하여 가능한 최대 골드를 갱신
  • return ans: 격자에서 얻을 수 있는 최대 골드를 반환

 

예제 

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

 

 

 

• 예를 들어, (1, 1) 위치:
  • grid[1][1] = 8에서 시작
  • 네 방향으로 이동하며 가능한 모든 경로를 탐색
  • (1, 2), (1, 0), (2, 1)로 이동하며 골드를 모음
  • 최대 골드를 찾음
• 모든 격자 위치에서 DFS를 실행하여 가능한 최대 골드를 찾습니다.
• 최대 골드는 24입니다 (경로: 8 -> 7 -> 9).

이런식으로 for문을 돌려 최대값을 찾음