[LeetCode 200] Numbers of Islands with JAVA

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

Number of Islands - LeetCode

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

 

class Solution {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int R;
    static int C;

    public int numIslands(char[][] grid) {
        R = grid.length;
        C = grid[0].length;
        int ans = 0;
        for (int i = 0; i < R; i++){
            for (int j = 0; j < C; j++){
                if (grid[i][j] == '1'){
                    dfs(grid, i, j);
                    ans++;
                }
            }
        }
        return ans;
    }
    public void dfs(char[][] grid, int r, int c) {
        grid[r][c] = '0';
        for (int i = 0; i < 4; i++){
            int newR = r + dr[i];
            int newC = c + dc[i];
            if (0 <= newR && newR < R && 0 <= newC && newC < C && grid[newR][newC] == '1'){
                dfs(grid, newR, newC);
            }
        }
    }
}

1. 어려웠던 점:

- 백준에서만 풀다가, leetcode 방식의 문제를 풀어, 처음엔 grid를 전역 변수 map에 복사하여 사용하였다.

이 후, 리팩토링. 알고리즘 풀이를 처음 배울 때, 한 번 실패했던 문제여서 시간은 엄청 짧게 걸렸다.

 

2. 알게된 점:

- DFS 복습

 

3. 알고리즘 풀이:

 - 대부분 visited 배열을 따로 두어, 이미 방문했던 곳인지 확인을 하지만 grid 배열에  '1'로 바꾸면 되기 때문에 그럴 필요가 없다.

첫 인덱스부터 마지막 인덱스까지 dfs를 돌며, 연결된 섬을 확인하고 dfs가 끝나면 1을 증가시키는 방식을 사용한다.