백준 4963 섬의 개수 (Java)

1. 문제 링크

4963번: 섬의 개수

 

2. 문제 및 입출력예제

 

3. 문제 풀이

8방으로 bfs 탐색을 진행한다.

섬의 시작이 어디부터인지 몰라서 8방으로 진행했다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.io.IOException;

public class Main {
	static int w, h;
	//상, 하, 좌, 우, 우상, 우하, 좌상, 좌하
	static int[] dx = {-1, 1, 0, 0, -1, 1, -1, 1}, dy = {0, 0, -1, 1, 1, 1, -1, -1};
	static boolean[][] map, visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] split;
		while(true) {
			split = br.readLine().split(" ");
			h = Integer.parseInt(split[0]);
			w = Integer.parseInt(split[1]);
			if(w==0 && h==0) {
				break;
			}
			map = new boolean[w][h];
			visit = new boolean[w][h];
			for(int i=0;i<w;i++) {
				split = br.readLine().split(" ");
				for(int j=0;j<h;j++) {
					
					if(split[j].equals("0")) {
						map[i][j] = false;
					}
					else {
						map[i][j] = true;
					}
				}
			}
			
			int result = 0;
			for(int i=0;i<w;i++) {
				for(int j=0;j<h;j++) {
					if(map[i][j] && !visit[i][j]) {
						bfs(i,j);
						result++;
					}
				}
			}
			sb.append(result).append("\n");
		}
		System.out.println(sb);
	}
	
	private static void bfs(int i, int j) {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.offer(new int[] {i, j});
		visit[i][j] = true;
		
		while(!queue.isEmpty()) {
			int[] now = queue.poll();
			
			for(int d=0;d<8;d++) {
				int X = now[0] +dx[d];
				int Y = now[1] +dy[d];
				if(X<0 | X>=w ||Y<0 || Y>=h || visit[X][Y] || !map[X][Y]) {
					continue;
				}
				queue.offer(new int[] {X,Y});
				visit[X][Y] = true;
			}
			
		}
	}
	
}