문제

입력

출력

예제

idea

모든 경우의 수를 탐색해야하기 때문에 완전 탐색 중 BFS를 생각하였다.
최종적으로 모든 섬이 visited 되어야 하기 때문에 for문을 통해서 visited 판별을 한 후 bfs를 돌렸고 bfs가 돌아가며 섬에 연결된 부분은 visited처리가 된다. 그 후 다른 !visited를 찾아낸 후 다시 bfs를 돌리는 방식으로 진행된다.

Code

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

public class Main {
	static Queue<int[]> queue =  new ArrayDeque<>();  
	static int y,x;
	static boolean visited[][];
	static int island[][];
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		while(true) {
			int num=0;
			st = new StringTokenizer(br.readLine());
			x= Integer.parseInt(st.nextToken());
			y= Integer.parseInt(st.nextToken());
			if(y==0&&x==0)
				break;
			visited = new boolean[y][x];
			
			island = new int[y][x];
			
			for (int i = 0; i < y; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < x; j++) {
					island[i][j]=Integer.parseInt(st.nextToken());
					if(island[i][j]==0)
						visited[i][j]=true;
				}
			}	
			
			for (int i = 0; i < y; i++) {
				for (int j = 0; j < x; j++) {
					if(!visited[i][j]) {
						bfs(i,j);
						num++;
					}
				}
			}
			System.out.println(num);
		}
	}
	
	static public void bfs(int q, int w) {
		
		int di[]= {0,1,0,-1,-1,1,1,-1};
		int dj[]= {1,0,-1,0,1,1,-1,-1};
		int dx=0,dy=0;
		
	
		queue.add(new int[] {q,w});
		
		while(!queue.isEmpty()) {
			int cur[] = queue.poll();
			for (int i = 0; i < 8; i++) {
				dy=cur[0]+di[i];
				dx=cur[1]+dj[i];
				
				if(dy<0||dx<0||dy>=y||dx>=x) continue;
				if(visited[dy][dx] || island[dy][dx]==0) continue;
				
				visited[dy][dx]=true;
				queue.add(new int[] {dy,dx});
			}			
		}				
	}
}

결과