[LeetCode- Ch7. DFS & BFS] 1. 섬의 수

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

Number of Islands - LeetCode

 

 

1.  BFS 이용 -> 큐    -> 너비우선

2. DFS 이용 -> 스택 -> 깊이우선

 

1. BFS 큐 이용

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

class Point{
    public int x, y;
    Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}
class Solution {
    static int answer=0, n,m, cnt;
    static char[][] arr;
    static boolean[][] check;
    static int[][] dis = {{1,0},{0,1},{-1,0},{0,-1}};

    public static int numIslands(char[][] grid) {

        //1은 땅, 0은 물
        n=grid.length;
        m=grid[0].length;

        cnt=0;
        check=new boolean[n][m];
        arr=grid;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]=='1' && check[i][j]==false){
                    cnt++;
                    System.out.println(cnt+" "+i+" "+j);
                    BFS(i,j);
                }
            }
        }
        return cnt;
    }
    public static boolean isValid(int x, int y){
        if(x<0 || y<0 || x>=n || y>=m) return false;
        return true;
    }
    public static void BFS(int x, int y){
        check[x][y]=true;
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(x,y));
        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;
                    q.offer(np);
                }
            }
        }
    }
}

 

2. DFS 스택 이용

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

class Point{
    public int x, y;
    Point(int x, int y){
        this.x=x;
        this.y=y;
    }
}
class Solution {
    static int answer=0, n,m, cnt;
    static char[][] arr;
    static boolean[][] check;
    static int[][] dis = {{1,0},{0,1},{-1,0},{0,-1}};

    public static int numIslands(char[][] grid) {

        //1은 땅, 0은 물
        n=grid.length;
        m=grid[0].length;
        cnt=0;
        
        check=new boolean[n][m];
        arr=grid;
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j]=='1'&& check[i][j]==false)
                DFS(new Point(i,j));
            }
        }
        
        return cnt;
    }
    public static boolean isValid(int x, int y){
        if(x<0 || y<0 || x>=n || y>=m) return false;
        return true;
    }
    public static void DFS(Point point){
        if(check[point.x][point.y]==false){
            cnt++;
        }        
         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;
                System.out.println(np.x+" "+np.y);
                DFS(np);
            }
        }
    }
}