Max Area of Island

📌 문제

• 해당 1의 면적 중, 1의 개수가 가장 많은 면적을 return 하기. 위의 문제에서는 주황색으로 칠해진 만큼인 6을 return

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

📌 문제 풀이

• 해당 값의 count의 상태를 알면서 나갈 때는 parameter로 넘기는 dfs보다 bfs가 더 편하다고 생각해서 bfs를 이용해서 풀었다.

📌 코드

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

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int i = solution.maxAreaOfIsland(new int[][]{
                {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}
        });
        System.out.println(i);
    }

    static class Solution {

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

        static int N;
        static int M;
        static int[][] map;
        public int maxAreaOfIsland(int[][] grid) {
            N = grid.length;
            M = grid[0].length;
            map = grid;
            int max = 0;

            for(int i=0;i<N;i++){
                for(int j=0;j<M;j++){
                    if(map[i][j]==1){
                        int count = bfs(i, j);
                        max = Math.max(count,max);
                    }
                }
            }
            return max;
        }

        private int bfs(int x, int y) {
            int cnt = 0;
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{x,y});
            cnt++;
            map[x][y] = 7;

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

                for(int d=0;d<4;d++){
                    int nx = poll[0] + dx[d];
                    int ny = poll[1] + dy[d];

                    if(isOut(nx,ny) || map[nx][ny] != 1) continue;

                    queue.offer(new int[]{nx,ny});
                    cnt++;
                    map[nx][ny] = 7;
                }
            }
            return cnt;
        }

        void print(){
            for(int i=0;i<N;i++){
                for(int j=0;j<M;j++){
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
        }
        boolean isOut(int nx,int ny){
            return nx<0 || ny <0 || nx>=N || ny>=M;
        }
    }
}