[LeetCode] 200. Number of Islands

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

LeetCode - The World's Leading Online Programming Learning Platform

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.

m x n 2D 이진 그리드 grid가 '1'(육지)과 '0'(물)의 지도를 나타냅니다. 섬의 개수를 반환하세요.
섬은 물에 둘러싸여 있으며, 수평 또는 수직으로 인접한 육지를 연결하여 형성됩니다. 그리드의 네 모서리가 모두 물로 둘러싸여 있다고 가정할 수 있습니다.

 

---

접근 방법

1. 문제 이해
‘1’은 육지고 ‘0’은 물입니다. 
4방향으로 이동하면서 육지 개수를 int로 반환합니다.
이때, 4방향으로 이동할 수 있다면 하나의 육지입니다.

 

2. 어떤 알고리즘을 써야 할까
grid를 다 탐색해야 하므로 완전탐색 - DFS를 사용합니다. 
- 임의로 (0,0)에서 시작합니다. → dfs(0,0)
- 육지 하나를 온전히 탐색하면 cnt++ 합니다.
- grid[r][c] == ‘1’인 곳 && 방문하지 않은 노드를 선택해 계속 탐색합니다.
- 모든 grid를 탐색합니다.

 

코드 구현

1. 실패 코드

class Solution { 
    static boolean[][] visited;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static int rowLength;
    static int colLength;

    public static boolean isValid(int r, int c, char[][] grid){
        return (r >= 0 && r < rowLength) && (c >= 0 && c < colLength) && (grid[r][c] == '1');
    }

    public static int numIslands(char[][] grid) {
        int cnt = 0;
        rowLength = grid.length;
        colLength = grid[0].length;
        visited = new boolean[rowLength][colLength];

        for(int i=0; i<rowLength; i++){
            for(int j=0; j<colLength; j++){
                    dfs(i,j,grid);
                    cnt++;
            }
        }
        return cnt;
    }

    public static void dfs(int r, int c, char[][] grid){
        visited[r][c] = true;
        for(int i=0; i<4; i++){
            int nextRow = r + dr[i];
            int nextCol = c + dc[i];

            if(isValid(nextRow,nextCol,grid)){
                if(!visited[nextRow][nextCol]) {
                    dfs(nextRow,nextCol,grid);
                }
            }
        }
    }
}

출력: 20
원인: 모든 노드를 dfs돌리면서 cnt++를 해주었기에 모든 노드의 개수를 반환한 것.
해결: 육지인 곳 그리고 아직 방문하지 않은 노드만 선별해서 dfs 돌리기.

 

2. 성공 코드

class Solution { 
    static boolean[][] visited;
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static int rowLength;
    static int colLength;
    
    public static boolean isValid(int r, int c, char[][] grid){
        return (r >= 0 && r < rowLength) && (c >= 0 && c < colLength) && (grid[r][c] == '1');
    }
    public static int numIslands(char[][] grid) {
        int cnt = 0;
        rowLength = grid.length;
        colLength = grid[0].length;
        visited = new boolean[rowLength][colLength];

        for(int i=0; i<rowLength; i++){
            for(int j=0; j<colLength; j++){
                if(grid[i][j] == '1' && (!visited[i][j])) {
                    dfs(i,j,grid);
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public static void dfs(int r, int c, char[][] grid){
        visited[r][c] = true;
        for(int i=0; i<4; i++){
            int nextRow = r + dr[i];
            int nextCol = c + dc[i];

            if(isValid(nextRow,nextCol,grid)){
                if(!visited[nextRow][nextCol]) {
                    dfs(nextRow,nextCol,grid);
                }
            }
        }
    }
}

 

배우게 된 점

1. DFS 템플릿 암기가 먼저, 응용은 암기 후에 가능한 영역이다.
2. 이 정도는 풀 수 있겠다! 자신감 가질 것!💪