Portfolio

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.

Example 1:


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
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:


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

Constraints:

m == grid.length

n == grid[i].length

1 <= m, n <= 50

grid[i][j] is either 0 or 1.

풀이

은찬


const maxAreaOfIsland = (grid) => {
    const m = grid.length;
    const n = grid[0].length;
    const visited = Array.from({length: m}, () => Array(n).fill(false));
    const direct = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    let answer = 0;
    
    const bfs = (sx, sy) => {
        const queue = [];
        let area = 1;
        
        queue.push([sx, sy]);
        visited[sx][sy] = true;
        
        while(queue.length){
            const [x, y] = queue.shift();

            for(let k = 0; k < 4; k++){
                const nx = x + direct[k][0];
                const ny = y + direct[k][1];

                if(nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] && !visited[nx][ny]){
                    area++;
                    queue.push([nx, ny]);
                    visited[nx][ny] = true;
                }
            }

            answer = answer < area ? area : answer;
        }
    }
    
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(grid[i][j] && !visited[i][j]){
                bfs(i, j);
            }
        }
    }
    
    return answer;
};

재영


const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // 4방

const maxAreaOfIsland = grid => {
    const rowLength = grid.length;
    const colLength = grid[0].length;

    let answer = 0; // 정답

    for (let i = 0; i < grid.length; i += 1) {
        for (let j = 0; j < grid[0].length; j += 1) {
            const queue = [];
            let cnt = 0;

            if (grid[i][j] === 1) {
                queue.push([i, j])
            }

            while (queue.length) {
                const [x, y] = queue.shift();

                if (!grid[x][y]) continue;
                grid[x][y] = 0;
                cnt += 1;
                
                for (let i = 0; i < 4; i += 1) {
                    const [dx, dy] = directions[i];
                    const nx = x + dx;
                    const ny = y + dy;

                    if (nx < 0 || ny < 0 || nx >= rowLength || ny >= colLength || !grid[nx][ny]) continue;
                    queue.push([nx, ny])
                }
            }

            answer = Math.max(answer, cnt)
        }
    }

    return answer; // 최대 개수
};

// 72ms, faster than 98%;

Max Area of Island

풀이