[Leetcode(릿코드)/200] Number of Islands (Medium, Java)

Question

• 문제 링크 : https://leetcode.com/problems/number-of-islands/
• 분류 : BFS
• 풀이 시간 : 12분

문제 해설

1. grid 2차원 배열 안 값 : 1(섬), 0(물)
2. 섬의 개수는 ?

Solution

풀이 접근 방법

1. 배열을 돌면서 섬을 마주치면, 해당 위치 기분으로 BFS 하면서 섬 탐색

정답 코드

class Solution {
    class Node {
        int x, y;
        
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public int N, M;
    public int[] dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
    
    public int numIslands(char[][] grid) {
        N = grid.length;
        M = grid[0].length;
        
        boolean[][] visited = new boolean[N][M];
        int count = 0;
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 섬 발견했는데 아직 방문 안한 섬이면 BFS로 섬 탐색
                if (grid[i][j] == '1' && !visited[i][j]) {
                    count++;
                    checkIsland(i, j, visited, grid);
                }
            }
        }
        
        return count;
    }
    
    public void checkIsland(int x, int y, boolean[][] visited, char[][] grid) {
        Queue<Node> queue = new LinkedList<Node>();
        
        visited[x][y] = true;
        queue.add(new Node(x, y));
        
        while(!queue.isEmpty()) {
            Node current = queue.poll();
            
            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];
                
                if (!isIn(nx, ny) || visited[nx][ny] || grid[nx][ny] == '0')
                    continue;
                
                visited[nx][ny] = true;
                queue.add(new Node(nx, ny));
            }
        } 
        
        return;  
    }
    
    public boolean isIn(int x, int y) {
        if (0 <= x && x < N && 0 <= y && y < M)
            return true;
        return false;
    }
}