Google #2 Number of Islands

Writer: Steven, Lee

Date: 1/27, Sunday

Purpose: Solving #200 Number of Islands

Level: Medium

Percentage: 39.7% have solved this problem

Time: it took me 30 minutes :)

Time Complexity: O(n^2) worst case

Runtime:  4 ms, faster than 70.04% of Java submissions

*The frequency of the problem that appears in the real interviews is more than 10% in 6 months *

한국어 버전은 밑에 있습니다.

* Caution * Before you read the solution that I used, you need to solve this problem by yourself 

* Description *

Given a 2d grid map of '1's (land) and '0's (water), count 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 *

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

* What is the Idea? *

 If you watch it carefully, you can realize that islands should be divided by '0' on horizontal and vertical. In other words, the Island should be formed by '1'. It would be perfect if we can know the boundary line. Then, Why not just traversal connecting adjacent '1' vertically and horizontally. Let me explain with the example :)

 Given islands map looks like this.

Input:
M:
1100
1100
0011
0001

If m[k] (Number k is in the range of the size of m) is '0', it should pass. if m[k] is '1', then we have to traversal m[k] until it contacts any '0' on horizontal and vertical or it's out of the range.

In this example, m[0][0] is '1' so we need to traversal here. then the shape looks like this 

1 1

1 1

m[0][1] is also '1'. but Is it necessary to do the same thing again?? the answer is "no" Because we know this '1 'is part of the island we've found. so we have to go next one.  

m[0][2], m[0][3] are '0' we don't need to do it here :)

m[1][0], m[1][1] are '1' but It's part of the island we've found. we don't need to do it here :)

m[1][2], m[1][3], m[2][0], m[2][1] are '0' we don't need to do it here :)

m[2][2] is '1' we need to do it here :) then, the shape looks like this.

1 1

  1

m[2][3] is '1' but It's part of the island we've found. we don't need to do it here :)

m[3][0], m[3][1], m[3][2], m[3][3] we don't need to do it :)

so the number of islands is '2'       

* Check *
you can check out your answer on this site.

https://leetcode.com/problems/number-of-islands/

(한국어)

* 난이도는 어려움입니다.

* 오직 39.7%만이 이 문제를 풀었습니다.

* 저는 30분 정도가 걸렸습니다. ^^/

* 시간 복잡도는 O(n^2)입니다. 

* 런타임은 4m로 제출자 70.04%보다 더 효율적입니다.  

 * 6개월 동안 실제 인터뷰에서 10% 이상이 출제가 되었습니다 *

* 주의 *  솔루션을 읽기 전에 스스로 문제를 푸실 수 있어야 합니다.

* 지문 *

 '1'은 땅 그리고 '0'은 물로 된 2d 격자판이 주어진다. 섬의 개수를 세어보아라. 섬은 물로 둘러싸여져 있으며 수직적으로 수평적으로 근접한 육지로 연결되어 구성한다. 또한 격자판의 네 개 모서리 밖은 모두 물로 되어 있다.

* 예시 *

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

* 아이디어 *

 만약 여러분이 이 문제를 자세히 본다면 섬들은 수직 그리고 수평에 있는 0으로 나누어져 있다는 것을 알 수 있습니다. 또 다른 말로 섬들은 "1"로 구성된다는 것입니다. 만약 우리가 경계선을 알 수 있다면 완벽할 것 같습니다. 그렇다면 그냥 수직, 수평에 있는 근접하고 연결된 "1"을 탐색하면 되지 않을까요? 예시와 함께 설명하겠습니다.

 주어진 섬의 지도는 다음과 같습니다.

Input:
M:
1100
1100
0011
0001  

만약 m[k] (숫자 k는 m의 사이즈의 범위입니다.)가 "0"이면 지나가면 됩니다. 만약 m[k]가 "1"이면 우리는 m[k]를 수직 그리고 수평에 있는 어떤 "0"을 만나거나 범위를 벗어날 때까지 탐색해야 합니다.

이 예시에서 m[0][0]은 "1"입니다. 그래서 우리들은 이 부분에서 탐색을 해야 합니다. 그러면 모양은 다음과 같이 나옵니다.

1 1                                                                                                                                                                                                       1 1 1

m[0][1] 또한 "1"입니다. 그러나 우리들이 똑같은 작업을 해야 할까요??? 대답은 NO입니다. 왜냐하면 우리는 이 "1"이 우리가 찾은 섬의 한 부분이라는 것을 알기 때문에 다음 부분으로 넘어가야 합니다.

m[0][2], m[0][3]은 '0'이기 때문에 작업을 할 필요가 없습니다.

m[1][0], m[1][1]은 "1"이지만 우리가 찾은 섬의 부분이기 때문에 여기서 작업할 필요가 없습니다.

m[1][2], m[1][3], m[2][0], m[2][1]은 '0'이기 때문에 작업을 할 필요가 없습니다.

m[2][2]는 "1"이기 때문에 여기서 작업을 해야 합니다. 모양은 다음과 같습니다.

1 1                                                                                                                                                                                                        1

m[2][3]은 "1"이지만 우리가 찾은 섬의 부분이기 때문에 여기서 작업할 필요가 없습니다.

m[3][0], m[3][1], m[3][2], m[3][3]에서 작업할 필요가 없습니다.

그래서 섬의 개수는 "2"입니다. 

* Check *
이 사이트에서 정답의 유무를 확인하실 수 있습니다.

https://leetcode.com/problems/number-of-islands/

 
 
public class NumberOfIslands_200 {
    public static int numIslands(char[][] grid) {
        if(grid == null || grid.length == 0) return 0;
        int islands = 0;
        boolean[][] map = new boolean[grid.length][grid[0].length];
        
        for(int i = 0 ; i < grid.length ; i++) {
            for(int j = 0 ; j < grid[0].length ; j++) {
                if(grid[i][j] == '1' && !map[i][j]) {
                    islandsSerach(grid, map, i, j);
                    islands++;
                }
            }
        }
        return islands;
    }
    public static void islandsSerach(char[][] grid, boolean[][] map, int i, int j) {
        if(i >= grid.length || j >= grid[0].length || i < 0 || j < 0 || grid[i][j] == '0' || map[i][j]) 
            return;
        map[i][j] = true;
    
        islandsSerach(grid, map, i+1, j);
        islandsSerach(grid, map, i, j+1);
        islandsSerach(grid, map, i-1, j);
        islandsSerach(grid, map, i, j-1);
        
        return;
    }
    
    public static void main(String[] args) {
        int res = numIslands(new char[][] {{'0','1','0','1','0'},
                                           {'1','1','0','1','0'},
                                           {'1','1','1','1','0'},
                                           {'0','1','0','0','1'}});
        System.out.println("Result: " + res);
    }
}