[LeetCode- Ch7. DFS & BFS] 3. 섬의 최대 면적

 

https://leetcode.com/problems/max-area-of-island/submissions/

Max Area of Island - LeetCode

 

 

1. 섬의 개수를 구한다.

2. 구한 섬의 개수를 이용해, BFS를 시작할때 1로 시작해 돌면서 한칸씩 추가한다.

 

class Point{
    public int x, y;
    Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}
class Solution {
    static int answer,n,m;
    static int[][] dis = {{1,0},{0,1},{-1,0},{0,-1}};
    static int[][] arr;
    static boolean[][] check;
    public int maxAreaOfIsland(int[][] grid) {
        n=grid.length;
        m=grid[0].length;
        check= new boolean[n][m];        
        arr=grid;
        answer=0;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]==1 && check[i][j]==false){
                    BFS(new Point(i,j));
                }
            }
        }
        return answer;
    }
    public boolean isValid(int x, int y){
        if(x<0 || y<0 || x>=n || y>=m){
            return false;
        }
        return true;
    }
    public void BFS(Point p){
        check[p.x][p.y]=true;
        Queue<Point> q = new LinkedList<>();
        q.offer(p);
        int cnt=1;
        answer=Math.max(answer, cnt);

        while(!q.isEmpty()){
            Point point=q.poll();
            for(int i=0;i<4;i++){
                Point np=new Point(point.x+dis[i][0], point.y+dis[i][1]);
                if(isValid(np.x, np.y) && check[np.x][np.y] == false && arr[np.x][np.y]==1)
                {
                    check[np.x][np.y]=true;
                    cnt++;  
                    answer=Math.max(answer, cnt);
                    q.offer(np);
                }
            }
        }
    }
}