백준 4963번 BFS

https://sonnnnnhnh.tistory.com/406

백준 4963번 DFS

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

public class Main {
	static int arr[][];  //섬 바다를 가질 배열
	static boolean visit[][];  //BFS방문여부
	static int dirX[] = {0, 0, -1 ,1, -1, 1, -1, 1}; // 상 하 좌 우 대각선 상좌, 상우, 하좌, 하우
	static int dirY[] = {-1, 1, 0, 0, 1, 1, -1, -1}; // 상 하 좌 우 대각선 상좌, 상우, 하좌, 하우

	static int w, h, nowX, nowY;  //넓이 높이 인접 섬의 넓이 높이 

	static class Node {   //q노드
		int x;
		int y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) throws Exception {
		StringBuilder sb = new StringBuilder();  //섬의 개수를 담는 StringBuilder 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
		StringTokenizer st;

		String str = " ";
		while( !(str = br.readLine()).equals("0 0") ) {  //테스트케이스 넓이가 00이면 안되므로 
			st = new StringTokenizer(str);


			w = Integer.parseInt(st.nextToken()); // 너비
			h = Integer.parseInt(st.nextToken()); // 높이
			arr = new int[h][w];
			visit = new boolean[h][w];

			for(int i=0; i<h; i++) {  //섬과 바다를 arr배열에 담는다
				st = new StringTokenizer(br.readLine());

				for(int j=0; j<w; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());

				}
			}

			int island_count = 0;  //섬개수 초기화
			for(int i=0; i<h; i++) {
				for(int j=0; j<w; j++) {
					
					if(!visit[i][j] && arr[i][j] == 1) {  //아직 방문하지 않고 1=섬이라면
						BFS(i, j);  
						island_count++;
					}
				}
			} 

			sb.append(island_count).append('\n');  //섬개수 출력후 줄바꿈
		}

		System.out.println(sb);
	} // End of main
	
	static void BFS(int x, int y) {
		Queue<Node> que = new LinkedList<Node>();  //node class를 담는 que
		visit[x][y] = true;  //방문
		que.offer(new Node(x, y));  //현재 섬의 좌표를 node class에 생성자에 넣고 que에 넣어줌
		
		while( !que.isEmpty() ) {
			Node node = que.poll();
		
			for(int i=0; i<8; i++) {
				nowX = dirX[i] + node.x;  //상하좌우대각선
				nowY = dirY[i] + node.y;

				if(range_check() && !visit[nowX][nowY] && arr[nowX][nowY] == 1) {  //인접 행렬을 방문하지 않았고 인접행렬이 섬인경우
					visit[nowX][nowY] = true;  //방문
					que.offer(new Node(nowX, nowY)); //다시 BFS
				}
			}
		}

	} // End of BFS;

	static boolean range_check() {
		return (nowX >= 0 && nowY >= 0 && nowX < h && nowY < w);  //배열 index 시작 0 끝 h w
	} // End of range_check
	
} // End of Main class

1.BFS이므로 que를 사용할것 

2.node class를 생성하여 매게변수로 섬의 좌표값을 넣고 그것을 que에 offer 하였음