[LeetCode] 200. Number of Islands

Problem

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'.

---

Solution

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++)
                if (grid[i][j] == '1') {
                    helper(grid, i, j);
                    count++;
                }
        return count;
    }
    private void helper(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || grid.length - 1 < i || grid[0].length - 1 < j || grid[i][j] == '0')
            return ;
        grid[i][j] = '0';
        helper(grid, i - 1, j);
        helper(grid, i, j - 1);
        helper(grid, i + 1, j);
        helper(grid, i, j + 1);
    }
}

Explanation

• 섬의 개수를 나타내는 변수 count를 선언한다.

  int count = 0;
  

• 배열 grid의 모든 요소를 참조하여 섬으로 구성되어 있는지를 판단하기 위하여 for 반복문을 작성한다.

  for (int i = 0; i < grid.length; i++)
    for (int j = 0; j < grid[0].length; j++)
  

• 상, 하, 좌, 우 4가지 방향 중 ‘1’이 포함되어있으면 다시 재귀함수를 호출하도록 재귀함수를 작성하여 섬을 구성하고 있는지를 확인한다.
• 배열 속에서 재귀함수를 호출한 요소는 다시 재귀함수를 호출할 필요가 없으므로 ‘0’으로 값을 바꾸 어주도록 한다.

  private void helper(char[][] grid, int i, int j) {
    grid[i][j] = '0';
    helper(grid, i - 1, j);
    helper(grid, i, j - 1);
    helper(grid, i + 1, j);
    helper(grid, i, j + 1);
  }
  

• 재귀함수가 멈출 수 있도록 if 조건문을 추가한다.

  if (i < 0 || j < 0 || grid.length - 1 < i || grid[0].length - 1 < j || grid[i][j] == '0')
    return ;
  

• 앞서 작성한 for 반복문 안에서 ‘1’을 발견하면 재귀함수를 호출하고, 호출한 재귀함수가 종료되면 섬의 개수를 증가시키도록 한다.

  if (grid[i][j] == '1') {
    helper(grid, i, j);
    count++;
  }