[LeetCode] 200. Number of Islands

[문제 링크]

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

 

[문제]

m x n 크기의 2D 그리드(grid)가 주어집니다. 그리드에서 '1'은 땅(land), 0'은 물(water)을 나타냅니다.

상하좌우로 연결된 '1'들이 하나의 섬을 형성합니다. 그리드에서 섬의 개수를 구하는 함수를 작성하세요.

[풀이 과정]

문제를 보자마자 DFS, BFS 문제인 것을 알았다.

그래서 연습겸 DFS로도 풀어보고 BFS로도 풀어보기로 했다.

 

[코드]

DFS 코드

class Solution {
    // 어디서든 사용해야하기 때문에
    private int x, y;
    private boolean[][] visited;
    private char[][] grid;
    
    public int numIslands(char[][] grid) {
        this.x = grid.length;
        this.y = grid[0].length;
        this.visited = new boolean[x][y];
        this.grid = grid;
        int answer = 0;

        for(int i = 0; i < x; i++) {
            for(int j = 0; j < y; j++) {
                if(grid[i][j] == '1' && visited[i][j] == false) {
                    visited[i][j] = true;
                    dfs(i, j);
                    answer++;
                }
            }
        }

        return answer;
    }


    public void dfs(int a, int b) {
        // 상하좌우 탐색하기 위해
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};

        for(int i = 0; i < 4; i++) {
            int next_x = a + dx[i];
            int next_y = b + dy[i];

            if(next_x >= 0 && next_y >= 0 && next_x < x && next_y < y && grid[next_x][next_y] == '1' && !visited[next_x][next_y]) {
                visited[next_x][next_y] = true;
                dfs(next_x, next_y);
            }
        }
    }
}

 

 

BFS 코드

class Solution {
    // 어디서든 사용해야하기 때문에
    private int x, y;
    private boolean[][] visited;
    private char[][] grid;
    
    public int numIslands(char[][] grid) {
        this.x = grid.length;
        this.y = grid[0].length;
        this.visited = new boolean[x][y];
        this.grid = grid;
        int answer = 0;

        for(int i = 0; i < x; i++) {
            for(int j = 0; j < y; j++) {
                if(grid[i][j] == '1' && visited[i][j] == false) {
                    visited[i][j] = true;
                    bfs(i, j);
                    answer++;
                }
            }
        }

        return answer;
    }


    public void bfs(int a, int b) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {a, b});

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

        while(!queue.isEmpty()) {
            int[] current = queue.poll();
            int xPos = current[0];
            int yPos = current[1];

            for(int i = 0; i < 4; i++) {
                
                int n_x = xPos + dx[i];
                int n_y = yPos + dy[i];

                if(n_x >= 0 && n_y >= 0 && n_x < x && n_y < y && !visited[n_x][n_y] && grid[n_x][n_y] == '1') {
                    visited[n_x][n_y] = true;
                    queue.offer(new int[] {n_x, n_y});
                }
            }
        }

    }
}

 

[회고]

생각보다 기본적인 DFS, BFS 문제라 쉬웠습니다.

DFS로 푸는게 더 쉬운 것 같았습니다.

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.