📌 DFS

• DFS - Stack - Recursion

for i <- 0 to row
 for j <- 0 to column
  if(grid[i][j]==1){
   count++
    bfs(grid,i,j) // = 역병함수
    }

• 역병함수 = 들어가면 근처에 있는 애들은 다 X로 변함

🔥 dfs method

private static void dfs(int[][] grid, int i, int j) {

    int row = grid.length;
    int column = grid[0].length;

    if(i<0||i>=row||j<0||j>=column || grid[i][j]!=1) return ;

    grid[i][j]=9;

    for(int[] k : dirs){
        dfs(grid,i+k[0],j+k[1]);
    }
}

recursion을 써줄거기 때문에 벗어나는 조건 명시
해당 값에 역병처리 해주고, 근처 상하좌우 돌려줌

🔥 전체 코드

public class NumberOfIsland_dfs {
    public static void main(String[] args) {
        int[][] grid = {
                {1,1,1,0,1},
                {1,1,0,0,0},
                {1,1,0,0,1},
                {0,0,0,0,1}
        };

        int solution = solution(grid);
        System.out.println("=====");

        System.out.println(solution);
    }

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

    private static int solution(int[][] grid) {
        if(grid==null || grid.length==0 || grid[0].length==0) return 0;

        int row = grid.length;
        int column = grid[0].length;

        int count=0;


        for(int i=0;i<row;i++){
            for(int j=0;j<column;j++){
                if(grid[i][j]==1){
                    count++;
                    dfs(grid,i,j);
                }
            }
        }
        print(grid);
        return count;
    }

    private static void dfs(int[][] grid, int i, int j) {

        int row = grid.length;
        int column = grid[0].length;

        if(i<0||i>=row||j<0||j>=column || grid[i][j]!=1) return ;

        grid[i][j]=7;

        for(int[] k : dirs){
            dfs(grid,i+k[0],j+k[1]);
        }
    }

    private static void print(int[][] grid){
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                System.out.print(grid[i][j] + " ");
            }
            System.out.println("");
        }
    }
}

📌 bfs

이것도 dfs와 같은 역병함수인데, Queue로 구현하는 것

🔥 bfs method

private static void bfs(int[][] grid, int i, int j) {
    Queue<int[]> q = new LinkedList<>();

    q.offer(new int[]{i, j});

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

        int x1 = poll[0];
        int y1 = poll[1];

        grid[x1][y1]=9;

        for (int[] dir : dirs) {
            int x2 = x1 + dir[0];
            int y2 = y1 + dir[1];

            if (x2 >= 0 && x2 < grid.length && y2 >= 0 && y2 < grid[0].length && grid[x2][y2] == 1) {
                q.offer(new int[]{x2, y2});
            }
        }
    }
}

• recursion을 쓰지 않기 때문에, 1을 마주할 때까지 계속 돌려줄 제약조건이 필요
  = !q.isEmpty()

• 상하좌우 + 한 값이 큐의 값이 범위값 안에 들어오면 큐에 값을 추가해줌