어떤 섬이 가장 큰 면적을 가지고 있는지 구하는 문제이다. 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)
i
와 j
, grid
범위에서 벗어나면 return 한다. grid[i][j]
셀을 0
으로 변경해 준다. (다시 탐색하지 않기 위해)grid[i][j]
가 1(섬)
일 경우에만 dfs
를 호출하도록 한다. dfs
의 결과를 result
에 담고 maxArea
에 저장된 (maxArea
의 초기값은 0
) 값과 비교하여 큰 수만 담아 계속 업데이트한다. 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;
};