[LeetCode] 200. Number of Islands

200. Number of Islands

LeetCode

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

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.

'1'(육지)와 '0'(물)로 이루어진 m x n 크기의 2차원 이진 격자 grid가 주어졌을 때, 섬(island)의 개수를 반환하시오.
섬은 물로 둘러싸여 있으며, 가로 또는 세로로 인접한 육지들이 연결되어 하나의 섬을 이룹니다.
또한 격자의 네 가장자리는 모두 물로 둘러싸여 있다고 가정해도 됩니다.

 

Example

Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]
Output: 1

Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]
Output: 3

---

1. 문제 요구사항 분석

0 사이에 둘러쌓여있는 1들의 묶음 찾기

2. 접근 전략

😁 bfs 사용해서, 배열을 돌면서 1을 발견하면 visited true 체크하고, 섬 개수 증가.

import java.util.*;

class Solution {
    public int numIslands(char[][] grid) {
        int island = 0;
        boolean[][] visited = 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' && !visited[i][j]) {
                    bfs(grid, i, j, visited);
                    island++;
                }
            }
        }

        return island;
    }

    public void bfs(char[][] grid, int i, int j, boolean[][] visited) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{i, j});
        visited[i][j] = true;

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx >= 0 && nx < grid.length &&
                    ny >= 0 && ny < grid[0].length &&
                    grid[nx][ny] == '1' &&
                    !visited[nx][ny]) {

                    queue.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }
}