Description
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.
문제 풀이
일단, 처음에는 어떤 방식으로 풀어야 할지 감이 잘 잡히지 않았다.
이전에 풀었던 문제인 최대 사각형의 넓이를 구하는 maximal-rectangle 의 해답인, 같은 열의 누적 합으로 어떻게 해볼 수 있지 않을까 싶었지만, 해답은 아닌 것 같았다.
고심끝에, 이중 for 문을 돌며 가장 처음 만난 "1" 의 위치에서 시작하여 위,아래,왼쪽,오른쪽을 재귀적으로 "2" 값으로 채워주는 방법을 생각해 냈다. (Island 의 한 점을 만나면 해당 Island 가 "2" 로 채워진다는 느낌으로)
소스 코드
class Solution {
public int numIslands(char[][] grid) {
int cnt = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == '1') {
fillIsland(grid, i, j);
cnt++;
}
}
}
return cnt;
}
private void fillIsland(char[][] grid, int row, int col) {
grid[row][col] = '2';
if (col - 1 >= 0 && grid[row][col - 1] == '1') {
fillIsland(grid, row, col - 1);
}
if (col + 1 < grid[0].length && grid[row][col + 1] == '1') {
fillIsland(grid, row, col + 1);
}
if (row - 1 >= 0 && grid[row - 1][col] == '1') {
fillIsland(grid, row - 1, col);
}
if (row + 1 < grid.length && grid[row + 1][col] == '1') {
fillIsland(grid, row + 1, col);
}
}
}다른 풀이 확인하기 위해 Discuss 를 보면서, 내가 풀어낸 방법이 이미 Flood Fill 이라는 알고리즘으로 존재하는 것을 알게 되었다.
