[알고리즘]백준4963 섬의 개수-java

1. 문제

2. 생각

그래프문제로 dfs와 bfs 두가지로 풀 수있다.

나는 bfs방식을 사용했다.

상하좌우대각선 총 8방향으로 섬이 연결된다.

한지점에서 8방향을 검사(이미 방문되엇는지and섬이있는지)
8방향 전부 검사 실패할때 count 1증가

모든지점 검사해서 미방문 and 섬존재 하는 지역이 없을경우 count출력

3. 코드

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

public class baekjoon4963 {
    static int dx[]=new int[]{0,0,-1,1,1,1,-1,-1};
    static int dy[]=new int[]{-1,1,0,0,-1,1,-1,1};
    static int iland[][];
    static boolean visit[][];
    static int startx;
    static int starty;
    static int n=1;
    static int m=1;
    
    public static void main(String []args){
        Scanner scan = new Scanner(System.in);
        
        while(n!=0 || m!=0){
            n=scan.nextInt();
            m=scan.nextInt();
            
            if(n==0 &&m==0){
                break;
            }
            int count=0;
            iland=new int[m+1][n+1];
            visit=new boolean[m+1][n+1];

            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    iland[i][j]=scan.nextInt();
                }
            }
            
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(visit[i][j]==false &&iland[i][j]==1){
                        bfs(i,j);
                        count++;
                    }
                }
            }
            
            System.out.println(count);
            
        }
    }
    
    public static void bfs(int i,int j){
        Queue<int[]> que = new LinkedList<>();

        que.add(new int[]{i,j});
        visit[i][j]=true;
        
        while(!que.isEmpty()){
            int a[]=que.poll();
            
            for(int w=0;w<8;w++){
                int ax=dx[w]+a[0];
                int ay=dy[w]+a[1];
                
                if(ax<0 || ay<0 || ax>m ||ay>n){
                    continue;
                }
                else if(iland[ax][ay]==1 && visit[ax][ay]==false){
                    que.add(new int[]{ax,ay});
                    visit[ax][ay]=true;
                }
            }
        }

    }
}