해당 포스팅은 릿코드 695번 Max Area of Island 풀이를 다룬다. 문제 링크

코드는 Javascript로 작성했고 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.

m x n 이진행렬 grid가 주어진다. 섬은 4방향으로 연결된 1(땅을 의미함)의 그룹이다. 섬의 면적은 섬에서 값이 1인 cell의 개수이다.

grid에서 섬의 최대 면적을 반환하자. 섬이 없으면 0을 반환하면 된다.

---

풀이

input으로 grid가 주어진다. 해당 grid의 cell을 방문하면서 1인 cell이 있으면 상하좌우로 1인 cell이 있는지 판별하는 작업을 반복해야 한다. 따라서 dfs로 풀이하면 된다. 이 때 이미 방문한 cell인지를 확인하기 위해 visited 배열을 만들어서 풀이하자.

---

로직 - DFS 이용

방문한 cell을 기록할 visited 배열을 만들자. 모든 원소를 false(방문 안 함)로 세팅한다.

const visited = [...Array(height)].map(() => Array(width).fill(false));

섬의 최대 면적을 기록할 변수 max를 0으로 세팅한다.

let max = 0;

grid를 loop 돌리면서 값이 1이며 아직 방문하지 않은 cell이 있다면 dfs해 섬의 면적을 구한다. dfs 종료 후 섬의 면적을 업데이트 한다.

for (let i=0; i<height; i++) {
  for (let j=0; j<width; j++) {
    if (grid[i][j] === 1 && !visited[i][j]) {
      const area = dfs(i,j, visited, grid);
      max = Math.max(max, area);
    }
  }
}

현재 방문한 cell을 방문처리 하고, 섬의 면적 area 변수를 정의한다.
그 다음 해당 cell의 면적을 더해주어야 하므로 area += 1을 해준다.

그리고 해당 cell의 상하좌우에 아직 방문하지 않은 값이 1인 cell이 있는지 확인하고 있다면 dfs한다. 상하좌우 cell 면적을 더해주기 위해 area += dfs(nx, ny, visited, grid)해준다.

function dfs(x, y, visited, grid) {
    const width = grid[0].length;
    const height = grid.length;
    
    let area = 0;
    visited[x][y] = true;
    area += 1;
    
    for (let k=0; k<4; k++) {
        const nx = x + dx[k];
        const ny = y + dy[k];
        const dfsCondition = nx >= 0 && ny >= 0 && nx < height && ny < width && grid[nx][ny] === 1 && !visited[nx][ny];
        
        if (dfsCondition) {
            area += dfs(nx, ny, visited, grid);
        }
    }
    return area;
}

---

전체 코드

/**
 * @param {number[][]} grid
 * @return {number}
 */

const dx=[-1, 0, 1, 0];
const dy=[0, 1, 0, -1];

var maxAreaOfIsland = function(grid) {
    const width = grid[0].length;
    const height = grid.length;
    const visited = [...Array(height)].map(() => Array(width).fill(false));
    let max = 0;
    
    for (let i=0; i<height; i++) {
        for (let j=0; j<width; j++) {
            if (grid[i][j] === 1 && !visited[i][j]) {
                const area = dfs(i,j, visited, grid);
                max = Math.max(max, area);
            }
        }
    }
    
    return max;
};

function dfs(x, y, visited, grid) {
    const width = grid[0].length;
    const height = grid.length;
    
    let area = 0;
    visited[x][y] = true;
    area += 1;
    
    for (let k=0; k<4; k++) {
        const nx = x + dx[k];
        const ny = y + dy[k];
        const dfsCondition = nx >= 0 && ny >= 0 && nx < height && ny < width && grid[nx][ny] === 1 && !visited[nx][ny];
        
        if (dfsCondition) {
            area += dfs(nx, ny, visited, grid);
        }
    }
    return area;
}