[LeetCode] 200. Number of Islands - Java

https://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'.

---

풀이

풀이 과정

땅(1)과 물(0)타일로 이루어진 2차원 배열이 주어질 때 물로 둘러 쌓여있는 땅, 즉 섬의 개수가 몇 개인지 구하는 문제이다.

주어진 각 타일에 대하여 타일이 땅(1)인 경우 섬 한개가 있다고 간주하며 해당 타일과 인접한 상하좌우 타일에 대해 dfs 탐색하며 해당 타일과 인접한 모든 땅(1) 타일을 물(0) 타일로 변경해가며 섬의 개수를 구한다.

탐색을 위해 그리드의 행과 열 값을 구한다.

// 그리드의 행과 열 값
int col = grid.length;
int row = grid[0].length;

 

정답값을 0으로 초기화 하고 그리드의 각 셀에 대하여 탐색을 실시한다.
이 때 해당 좌표에 해당하는 값이 땅(1)인 경우 정답 카운트를 증가시키고 현재 좌표와 이어진 모든 타일을 dfs 탐색한다.

int answer = 0;

// 그리드의 각 셀을 탐색
for(int i = 0; i < col; i++){
    for(int j = 0; j < row; j++){
        // 해당 좌표가 땅(1)인 경우
        if(grid[i][j] == '1'){
            // 정답 카운트 증가
            answer++;
            // 현재 좌표와 이어진 모든 땅을 탐색
            dfs(grid, i, j);
        }
    }
}

 

dfs 탐색은 탐색 대상이 되는 2차원 배열, x좌표, y좌표를 인자로 받으며 좌표가 그리드를 벗어나는 경우 탐색을 종료한다.
좌표가 그리드 내에 존재하는 경우 해당 타일이 땅(1)인 경우 물(0)로 변경하고 인접하는 상하좌우 타일에 대해 다시 dfs 탐색을 실시한다.

public void dfs(char[][] grid, int x, int y){
    // 좌표가 그리드를 벗어나는 경우 탐색 종료
    if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) return;
    // 방문한 타일이 땅(1)인 경우 물(0)로 변경
    // 상하좌우 타일 탐색하며 모든 인접한 땅타일을 물로 변경
    if(grid[x][y] == '1'){
        grid[x][y] = '0';
        dfs(grid, x, y+1);
        dfs(grid, x, y-1);
        dfs(grid, x+1, y);
        dfs(grid, x-1, y);
    }
}

 

탐색이 종료되면 최종 정답을 반환한다.

return answer;

---

최종 코드

class Solution {
    public int numIslands(char[][] grid) {
        // 그리드의 행과 열 값
        int col = grid.length;
        int row = grid[0].length;

        int answer = 0;

        // 그리드의 각 셀을 탐색
        for(int i = 0; i < col; i++){
            for(int j = 0; j < row; j++){
                // 해당 좌표가 땅(1)인 경우
                if(grid[i][j] == '1'){
                    // 정답 카운트 증가
                    answer++;
                    // 현재 좌표와 이어진 모든 땅을 탐색
                    dfs(grid, i, j);
                }
            }
        }

        return answer;
    }

    public void dfs(char[][] grid, int x, int y){
        // 좌표가 그리드를 벗어나는 경우 탐색 종료
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) return;
        // 방문한 타일이 땅(1)인 경우 물(0)로 변경
        // 상하좌우 타일 탐색하며 모든 인접한 땅타일을 물로 변경
        if(grid[x][y] == '1'){
            grid[x][y] = '0';
            dfs(grid, x, y+1);
            dfs(grid, x, y-1);
            dfs(grid, x+1, y);
            dfs(grid, x-1, y);
        }
    }
}

---