# Find the number of Islands using DFS.

### Count total number of Islands ORThe "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

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