[BAEKJOON] 4963번 섬의 개수

---

 

이차원 배열에 섬과 바다를 저장하고, 방문하지 않은 섬일 경우 bfs 방식으로 방문할 수 있는 모든 섬들을 방문처리하며 한 번의 호출로 갈 수 있는 섬들을 모두 방문한다.

특히 중요한 점이 대각선 방향으로도 섬과 섬 사이를 이동할 수 있으므로 8가지 방향으로 나아갈 수 있도록 8번의 반복문으로 다음 방문할 섬을 선택하도록 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int cnt, arr[][], h, w;
	static int dx[] = {-1,-1,-1,0,0,1,1,1};
	static int dy[] = {-1,0,1,-1,1,-1,0,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String escape = br.readLine();
		while(!escape.equals("0 0")) {
			StringTokenizer st = new StringTokenizer(escape);
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			arr = new int[h][w];
			
			for(int i=0; i<h; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<w; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken()); // 1이면 섬, 0이면 바다
				}
			}
			cnt = 0;
			for(int i=0; i<h; i++) {
				for(int j=0; j<w; j++) {
					if(arr[i][j]==1) { // 방문하지 않은 섬일 경우
						bfs(i,j);
						cnt++;
					}
				}
			}
			System.out.println(cnt);
			escape = br.readLine();
		}
	}
	static void bfs(int i, int j) {
		Queue<Point> q = new LinkedList<>();
		q.add(new Point(i , j));
		arr[i][j] = 2; // 2로 방문처리
		
		while(!q.isEmpty()) {
			Point now = q.poll();
			int nowx = now.x;
			int nowy = now.y;
			// 8가지 방향으로 갈 수 있는 섬 탐색
			for(int k=0; k<8; k++) {
				int nextX = nowx + dx[k];
				int nextY = nowy + dy[k];
				
				if(nextX>=0 && nextY>=0 && nextX<h && nextY<w && arr[nextX][nextY]==1) {
					arr[nextX][nextY] = 2; // 2로 방문처리
					q.add(new Point(nextX, nextY));
				}
			}
		}
	}
	
	static class Point{
		int x,y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}

[출처]

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

4963번: 섬의 개수