Number of Islands

🔗 문제 링크

https://leetcode.com/problems/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.

⚠️ 제한사항

• $m = grid.length$

• $n = grid[i].length$

• $1 <= m, n <= 300$

• $grid[i][j]$ is '0' or '1'.

---

🗝 풀이 (언어 : Java)

DFS 문제이다. 해당 2차원 배열의 가로, 세로 길이와 과거에 방문했는지 여부를 체크하는 2차원 배열 그리고 정답을 카운트할 변수를 전역으로 선언해주고, 이중 반복문으로 모든 경우의 수를 돈다. 해당 순서의 지점이 체크했던 지점이거나(과거의 섬과 같은 소속의 땅), 물인 경우에 skip하고 아니면 정답을 카운트해주고 해당 지점과 같은 섬인 땅을 상하좌우 재귀적으로 찾아서 방문 체크 2차원 배열을 갱신해준다. 아래는 BFS로도 풀어본 풀이다.

DFS

class Solution {
    // 섬 개수, 전체 가로, 세로 길이
    private int count, vertical, horizontal;
    // 방문한 지점을 이미 체크했는지 여부
    private boolean[][] visited;
    // 해당 지점과 상하좌우로 붙어 있어서 같은 섬인 경우 방문 체크
    private void dfs(char[][] grid, int i, int j) {
        // 범위 넘거나, 이미 체크한 땅인 경우
        if (i < 0 || i >= vertical || j < 0 || j >= horizontal || visited[i][j] == true || grid[i][j] == '0')
            return;
        // 아니면 방문 체크하고 상하좌우 체크 반복
        visited[i][j] = true;
        dfs(grid, i-1, j);
        dfs(grid, i+1, j);
        dfs(grid, i, j-1);
        dfs(grid, i, j+1);
    }

    public int numIslands(char[][] grid) {
        vertical = grid.length;
        horizontal = grid[0].length;
        visited = new boolean[vertical][horizontal];
        for (int i = 0; i < vertical; i++) {
            for (int j = 0; j < horizontal; j++) {
                // 해당 지점이 물이 아니고, 전에 체크 안했던 지점인 경우 전체 섬의 수 + 1
                if (grid[i][j] == '1' && visited[i][j] == false) {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
}

BFS

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    // 섬 개수, 전체 가로, 세로 길이
    private int count, vertical, horizontal;
    // 방문한 지점을 이미 체크했는지 여부
    private boolean[][] visited;
    // 해당 지점과 상하좌우로 붙어 있어서 같은 섬인 경우 방문 체크
    private void bfs(char[][] grid, int i, int j) {
        // bfs의 체크 순서를 저장할 큐
        Queue<int[]> queue = new LinkedList<>();
        // 처음 지점을 큐에 넣고 시작, 방문여부도 체크
        queue.offer(new int[] {i, j});
        visited[i][j] = true;
        // 큐에 들어간 해당 지점의 상하좌우 지점들을 큐에 계속 넣는다, 큐안에 원소가 없을 때까지 반복
        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            int v = point[0], h = point[1];
            // 상
            if (v-1 >= 0 && v-1 < vertical && h >= 0 && h < horizontal && visited[v-1][h] == false && grid[v-1][h] == '1') {
                visited[v-1][h] = true;
                queue.offer(new int[] {v-1, h});
            }
            // 하
            if (v+1 >= 0 && v+1 < vertical && h >= 0 && h < horizontal && visited[v+1][h] == false && grid[v+1][h] == '1') {
                visited[v+1][h] = true;
                queue.offer(new int[] {v+1, h});
            }
            // 좌
            if (v >= 0 && v < vertical && h-1 >= 0 && h-1 < horizontal && visited[v][h-1] == false && grid[v][h-1] == '1') {
                visited[v][h-1] = true;
                queue.offer(new int[] {v, h-1});
            }
            // 우
            if (v >= 0 && v < vertical && h+1 >= 0 && h+1 < horizontal && visited[v][h+1] == false && grid[v][h+1] == '1') {
                visited[v][h+1] = true;
                queue.offer(new int[] {v, h+1});
            }
        }
    }

    public int numIslands(char[][] grid) {
        vertical = grid.length;
        horizontal = grid[0].length;
        visited = new boolean[vertical][horizontal];
        for (int i = 0; i < vertical; i++) {
            for (int j = 0; j < horizontal; j++) {
                // 해당 지점이 물이 아니고, 전에 체크 안했던 지점인 경우 전체 섬의 수 + 1
                if (grid[i][j] == '1' && visited[i][j] == false) {
                    count++;
                    bfs(grid, i, j);
                }
            }
        }
        return count;
    }
}