문제

LeetCode - Number of Islands

Code

1차 풀이 - BFS

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int numIslands(char[][] grid) {
        int answer = 0;
        int m = grid.length;
        int n = grid[0].length;

        int[][] visited = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j] == 0 && grid[i][j] == '1') {
                    visited = searchBFS(grid, visited, i, j);
                    answer += 1;
                }
            }
        }
        return answer;
    }

    public int[][] searchBFS(char[][] grid, int[][] visited, int r, int c) {
        int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        Queue<int[]> dq = new ArrayDeque<>();
        dq.offer(new int[]{r, c});
        visited[r][c] = 1;

        while (!dq.isEmpty()) {
            int[] curr = dq.poll();

            for (int[] dir : dirs) {
                int nx = curr[0] + dir[0];
                int ny = curr[1] + dir[1];

                if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length) continue;
                if (visited[nx][ny] == 1 || grid[nx][ny] == '0') continue;

                visited[nx][ny] = 1;
                dq.offer(new int[]{nx, ny});

            }
        }
        return visited;
    }
}

• BFS를 이용한 풀이이다.
• Grid 범위 안에 있고, 방문하지 않고 육지인 경우들을 탐색한다.

2차 풀이 - DFS

class Solution {
    public int numIslands(char[][] grid) {
        int answer = 0;
        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    searchDFS(grid, i, j);
                    answer += 1;
                }
            }
        }
        return answer;
    }

    public void searchDFS(char[][] grid, int r, int c){
        grid[r][c] = '0';
        int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        for (int[] dir: dirs){
            int nr = r + dir[0];
            int nc = c + dir[1];

            if (nr < 0 || nr >= grid.length || nc < 0 || nc >= grid[0].length) continue;
            if (grid[nr][nc] == '1') searchDFS(grid, nr, nc);
        }
    }
}

• DFS를 이용한 풀이이다.
  • 재귀를 이용하여 탐색을 진행하였다.
  • visited를 따로 두지 않고, 기존 grid의 값을 변경하는 방법으로 진행하였다.