[백준] 섬의 개수 4963 - JAVA

문제

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

코드

BFS 문제

import java.util.*;
import java.io.*;

public class Main {
	
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		while(true) {
			st = new StringTokenizer(br.readLine());
			int w = Integer.parseInt(st.nextToken());
			int h = Integer.parseInt(st.nextToken());
			
			if(w == 0 && h == 0)
				break;
			
			int board [][] = new int[h+1][w+1];
			for(int i=1;i<=h;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=1;j<=w;j++) {
					board[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			sb.append(bfs(board, w, h)+"\n");
			

		}
		
		
		System.out.print(sb);
	}
   
	static int bfs(int board[][], int w, int h) {
		boolean visited [][] = new boolean[h+1][w+1];
		
		int dx [] = {1, 0, -1, 0, 1, 1, -1, -1};
		int dy [] = {0, 1, 0, -1, 1, -1, 1, -1};
		
		int count = 0;
		
		for(int i=1; i <= h; i++) {
			for(int j=1; j <= w; j++) {
				Queue<int []> que = new LinkedList<>();
				
				if(visited[i][j] || board[i][j] == 0) continue;
				
				count++;
				
				que.add(new int[] {i, j});
				visited[i][j] = true;
				
				while(!que.isEmpty()) {
					int now [] = que.poll();
					
					for(int k=0;k<8;k++) {
						int nx = now[0] + dx[k];
						int ny = now[1] + dy[k];
						
						if(nx < 1||ny<1|| nx > h || ny > w) continue;
						if(visited[nx][ny] || board[nx][ny] == 0) continue;
						
						que.add(new int[] {nx, ny});
						visited[nx][ny] = true;
					}
				}
				
				
			}
		}
		
		return count;
	}
	
   
}