Find the number of Islands using DFS.

Count total number of Islands OR
The "Island Count" Problem

---

Given a Ocean in a form of 2D matrix as shown below in which there are few Island present 
(or may not be present).

In a matrix given above, which has only two values ‘1’ and ‘0’. 
1 represents land and 
0 represents water, 
Find the total number of Islands.

Lets understand what is the input and the expected output with few samples.

Sample 1:
Input: 
        int[][] island = new int[][] {
                { 1, 1, 0, 0, 0 },
                { 0, 1, 0, 0, 1 },
                { 1, 0, 0, 1, 1 },
                { 0, 0, 0, 0, 0 },
                { 1, 0, 1, 0, 1 }             
        }; Output: 5

Sample 2:
Input:
        int[][] island = new int[][] {
                {0, 0, 0, 0, 0 },
                {0, 0, 0, 0, 0 },
                {0, 0, 0, 0, 0 },
                {0, 0, 0, 0, 0 },
                {0, 0, 0, 0, 0 }               
        };
Output:0

Sample 3:
Input:
        int[][] island = new int[][] {
                { 1, 0, 0, 0, 0 },
                { 0, 1, 0, 0, 0 },
                { 0, 0, 1, 0, 0 },
                { 0, 0, 0, 0, 0 },
                { 1, 1, 1, 0, 0 }                  
        };
Output:2

Algorithm

---

To count number of Island, we need to start exploring matrix element one by one.

1. If encountered element is '0', no need to take any action, go next.
2. As soon you encounter '1, it means land has started, How long this land is connected that we don't know, Fo that purpose, we need to check all 8 sides of coordinate representing land.

We will use Depth first search for each coordinate and if we encounter land coordinate that is '1', 
we will make it '*' just an identification that we already visited this element. 

In Depth first search, we continue checking elements till first land element that is '1' is not encountered. 

As soon as we encounter 1, Say we encounter '1' at (1,1), We will start checking all 8 adjacent coordinates of (1,1)

1. "Right coordinate" (row, col+1), 
2. "Bottom-Right diagonal" (row+1, col+1), 
3. "Bottom" (row+1, col), 
4. "Bottom-Left diagonal" (row+1, col-1), 
5. "Left" (row, col-1), 
6. "Top-Left diagonal" (row-1, col-1), 
7. "Top" (row-1, col), 
8. "Top-Right diagonal" (row-1, col+1).

While exploring adjacent sides, if we encounter '1' in any one of the adjacent sides say Right (1,2) then Process continues from first step again for new coordinate (1,2).

Say we covered all adjacent sides of (1,2), then we will again backtrack to caller, (1,1) and it continues exploring remaining adjacent sides of (1,1).

Also, when all adjacent sides are explored, we will increment our counter++, as indication that 1 island is covered.

Let's take one sample example to understand in better way, pointer is at (0,0)

(0,0) is 1, it means it is a Land, so let's explore all 8 adjacent coordinates of (0,0).

After exploring all adjacent sides of (0,0), recursion comes back to (0,0) and we will explore next element (0,1) and it continues counting all the island encountered.

Java Program to find the number of Islands.

---

package com.javabypatel;

public class CountNumberOfIslandPart {
 public static void main(String[] args) {

  int[][] island = new int[][] {
    { 1, 1, 0, 0, 0 },
    { 0, 1, 0, 0, 1 },
    { 1, 0, 0, 1, 1 },
    { 0, 0, 0, 0, 0 },
    { 1, 0, 1, 0, 1 }       
  };
  System.out.println(countIsland(island));

  //If required, change '*' back to 1 in matrix.
 }

 public static int countIsland(int[][] island){
  if(island == null){
   return 0;
  }
  int count = 0;
  for (int i = 0; i < island.length; i++) {
   for (int j = 0; j < island[i].length; j++) {

    if(island[i][j] == 1){
     markAllNeighours(i, j, island);
     count++;
    }
   }
  }
  return count;
 }

 public static void markAllNeighours(int row, int col, int[][] island){

  island[row][col] = '*';

  //Right
  if(col+1 < island[row].length && island[row][col+1] == 1)
   markAllNeighours(row, col+1, island);

  //Bottom Right diagonal
  if(row+1 < island.length && col+1 < island[row].length && island[row+1][col+1] == 1)
   markAllNeighours(row+1, col+1, island);

  //Bottom
  if(row+1 < island.length && island[row+1][col] == 1)
   markAllNeighours(row+1, col, island);

  //Bottom Left diagonal
  if(row+1 < island.length && col-1 >= 0 && island[row+1][col-1] == 1)
   markAllNeighours(row+1, col-1, island);

  //Left
  if(col-1 >= 0 && island[row][col-1] == 1)
   markAllNeighours(row, col-1, island);

  //Top Left diagonal
  if(row-1 >= 0 && col-1 >= 0 && island[row-1][col-1] == 1)
   markAllNeighours(row-1, col-1, island);

  //Top
  if(row-1 >= 0 && island[row-1][col] == 1)
   markAllNeighours(row-1, col, island);

  //Top Right diagonal
  if(row-1 >= 0 && col+1 < island[row].length && island[row-1][col+1] == 1)
   markAllNeighours(row-1, col+1, island);
 }
}

You may also like to see

---

Count number of islands where every island is row-wise and column-wise separated

---

0/1 Knapsack Problem solved using Iterative and Dynamic Programming

The Skyline Problem

Stock Buy Sell to Maximize Profit.

Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted

Count trailing zeros in factorial of a number.

How to Detect loop in linked list.

Tower Of Hanoi Program in Java.

Print Matrix Diagonally OR Diagonal order of Matrix.

Implement Queue using One Stack in Java (Recursive Implementation)

SOAP Vs REST Web Service, when to use SOAP, When to use REST.

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.