문제 정리

---

주어진 배열에서 섬의 개수를 세야한다
상하좌우 대각선 까지 같은 섬으로 취급 -> 8방향 탐색

입력

테스트 케이스 1
너비 높이
맵 정보
테스트 케이스 2
너비 높이
맵 정보
…
0 0 //입력 값 끝

출력

테스트 케이스 1의 섬 개수
테스트 케이스 2의 섬 개수
…

idea 정리

---

이미 여러번 풀어본 문제의 유형이라 알고리즘 구성은 어렵지 않았다
bfs를 이용해 시작점에서 연결된 지점을 다 돌면서 방문 처리를 해준다
방문 처리가 안된 시작점을 찾아서 반복하면 된다
섬의 개수는 방문 처리가 안된 시작점의 개수가 된다

알고리즘 구성

---

1. 배열을 입력 받는다
2. 배열을 돌면서 방문처리가 안 된 곳을 찾는다
3. 방문처리가 안된 곳을 시작으로 bfs를 한다
4. bfs로 돈 곳은 모두 방문 처리를 한다
5. 현재 bfs가 끝나면 방문처리가 안 된 섬이 없을 때 까지 2~4 반복

구현

---

//섬의 개수
public class Main {
	static int H, W;
	static int[][] map;
	static boolean[][] visited;
	
	static int[] dr = {-1, -1, -1, 0, 1, 1, 1, 0};
	static int[] dc = {-1, 0, 1, 1, 1, 0, -1, -1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String input = br.readLine();
		
		while(!input.equals("0 0")) {
			StringTokenizer st = new StringTokenizer(input, " ");
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			
			map = new int[H][W];
			visited = new boolean[H][W];
			
			for(int i=0; i<H; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for(int j=0; j<W; j++) {
					int value= Integer.parseInt(st.nextToken());
					map[i][j] = value;
				}
			}
			
			int res = 0;
			for(int i=0; i<H; i++) {
				for(int j=0; j<W; j++) {
					if(!visited[i][j] && map[i][j]==1) {		//아직 방문 안 한 섬만 bfs
						bfs(i, j);
						res++;
					}
				}
			}
			
			bw.write(res + "\n");
			input = br.readLine();		//0 0 나올때까지 받아야하므로
		}//end of while
        
		bw.flush();
		bw.close();
		br.close();
	}
	
	static void bfs(int r, int c) {
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(c, r));
		visited[r][c] = true;
		
		while(!q.isEmpty()) {
			Point now = q.poll();
			
			for(int i=0, size=dr.length; i<size; i++) {
				int nr = now.y + dr[i];
				int nc = now.x + dc[i];
				
				if(0>nr | nr>=H | 0>nc | nc>=W) continue;		//범위를 벗어나는곳
				if(visited[nr][nc] || map[nr][nc]==0) continue;	//이미 방문했거나 바다인 곳
				
				q.offer(new Point(nc, nr));
				visited[nr][nc] = true;
			}
		}//end of while
	}
}

#결과