[LeetCode] Number of Islands

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.lengthn == grid[i].length1 <= m, n <= 300grid[i][j] is '0' or '1'.

 

이번 문제는 전형적인 DFS 문제라고 생각 할 수 있습니다.

 

섬의 갯수를 구하는 것인데요. 일반적으로 사각형 개수 구하기 등으로 문제 출제도 되는 편입니다.

저는 방문 기록을 나타내는 visit 라는 2차원 배열을 선언하였습니다.

 

dfs라는 메서드를 호출 하기 전 방문한 섬이 '1'인 경우에 answer를 증가시킵니다.

 

그리고 dfs 재귀를 돌면서 인접한 '1'을 모두 방문하도록 합니다.

 

이후 for loop를 통해 방문한 적이 없고, 원소가 '1'인 경우 다시 answer를 증가시키고 인접한 '1'을 모두 방문합니다.

만약 방문하였는데 '0'인 경우 방문 표시만 남기고 카운트를 증가시키지 않습니다.

 

dfs에서는 메서드 내부에서는 재귀를 빠져나오도록 하구요.

퍼포먼스는 그리 좋은 점수를 받지 않았습니다.

 

아래는 코드입니다.

 

class Solution {
    public int numIslands(char[][] grid) {
        int answer = 0;
        boolean[][] visit = new boolean[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (visit[i][j]) {
                    continue;
                }

                if (grid[i][j] == '0') {
                    visit[i][j] = true;
                    continue;
                }

                answer++;
                dfs(grid, visit, i, j);
            }
        }
        return answer;
    }

    private void dfs(char[][] grid, boolean[][] visit, int x, int y) {
        if (visit[x][y]) {
            return;
        }

        visit[x][y] = true;

        if (grid[x][y] == '1') {
            if (x > 0) {
                dfs(grid, visit, x - 1, y);
            }
            if (y > 0) {
                dfs(grid, visit, x, y - 1);
            }
            if (x < grid.length - 1) {
                dfs(grid, visit, x + 1, y);
            }
            if (y < grid[x].length - 1) {
                dfs(grid, visit, x, y + 1);
            }
        }
    }
}