DFS 문제

문제 설명

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

상하좌우로 움직이며 바다에 떠있는 가장 큰 섬의 면적을 구하면된다.

코드

var maxAreaOfIsland = function (grid) {
  let result = 0;
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === 1) {
        const max = dfs(grid, i, j);
        result = Math.max(max, result);
      }
    }
  }
  return result;
};

function dfs(grid, i, j, max = 0) {
  if (!grid[i] || !grid[i][j]) return max;

  grid[i][j] = 0;
  return (
    1 +
    dfs(grid, i, j + 1, max) +
    dfs(grid, i + 1, j, max) +
    dfs(grid, i - 1, j, max) +
    dfs(grid, i, j - 1, max)
  );
}

한칸 한칸 체크하면서 1일 때(섬의 시작 점) DFS로 탐색을 시작한다.

상하좌우의 움직임이 Grid를 벗어나면 return 한다.

1을 0으로 바꾸어 방문 표시

상하좌우로 움직여 섬의 면적을 계산한다.

1을 더하는 이유는 처음 시작의 값이기 때문이다.

1. Max Area of Island

페이지 이동