695. Max Area of Island

695. Max Area of Island

문제

어떤 섬이 가장 큰 면적을 가지고 있는지 구하는 문제이다. DFS로 섬을 탐색하여 면적을 계산하고 maxArea에 저장된 값 중 가장 큰 값을 반환한다.

테스트 케이스

Input: grid = [
	[0,0,1,0,0,0,0,1,0,0,0,0,0],
    [0,0,0,0,0,0,0,1,1,1,0,0,0],
    [0,1,1,0,1,0,0,0,0,0,0,0,0],
    [0,1,0,0,1,1,0,0,1,0,1,0,0],
    [0,1,0,0,1,1,0,0,1,1,1,0,0],
    [0,0,0,0,0,0,0,0,0,0,1,0,0],
    [0,0,0,0,0,0,0,1,1,1,0,0,0],
    [0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6

👉 답이 11이 아닌 이유는 우측 아래 두 섬이 상하좌우로 이웃한 섬이 아니기 때문에 좌표 3, 8로 시작하는 섬의 면적이 6으로 가장 크다.

풀이

DFS(grid, i, j)

1. 가장 먼저 재귀적으로 이웃한 셀을 탐색할 DFS의 탈출 조건을 만들어 준다. i와 j, grid 범위에서 벗어나면 return 한다.
2. 현재 i와 j의 위치를 더해주기 때문에 먼저 현재 도달한 grid[i][j] 셀을 0으로 변경해 준다. (다시 탐색하지 않기 위해)
3. 상하좌우로 이웃한 섬이 있는지 확인하기 위해 좌표를 상하좌우로 이동시켜 재귀적으로 dfs를 호출한다.
4. 면적의 합을 return 한다.

반복문으로 grid 셀 탐색

1. 2차원 배열인 grid를 탐색하기 위해 이중 반복문을 사용한다. grid[i][j]가 1(섬)일 경우에만 dfs를 호출하도록 한다.
2. 재귀적으로 탐색을 마친(=모든 섬의 면적을 계산하면) dfs의 결과를 result에 담고 maxArea에 저장된 (maxArea의 초기값은 0) 값과 비교하여 큰 수만 담아 계속 업데이트한다.
3. 모든 섬의 탐색을 마치면 maxArea를 반환한다.

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
  let maxArea = 0;

  function dfs(grid, i, j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === 0) {
        return 0;
    }
    grid[i][j] = 0;
    let sum = 1 + dfs(grid, i+1, j) + dfs(grid, i-1, j) + dfs(grid, i, j+1) + dfs(grid, i, j-1)
    console.log('Sum is', sum)
    return sum;
  }

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

  return maxArea;
};