/ BOJ

BOJ_4963_섬의개수_JAVA

문제 : 섬의 개수

링크 : BOJ_4963_섬의개수

접근 방식

2차원 배열에서 섬의 개수를 구해야 하는 문제이다. BFS로 바다가 아닌 부분을 탐색하는데, BFS를 돌리는 조건을 땅인 경우 + 아직 방문하지 않은 경우로 하여 bfs를 돌리게 되면, 섬의 개수가 추려지게 된다.

소스 코드

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 BOJ_4963_섬의개수 {

	static int N, M, arr[][];

	static boolean visited[][];

	static int dir[][] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st;
		while (true) {
			st = new StringTokenizer(in.readLine());
			M = Integer.parseInt(st.nextToken());

			N = Integer.parseInt(st.nextToken());

			if (M == 0 && N == 0) {
				return;
			}
			arr = new int[N][M];
			visited = new boolean[N][M];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(in.readLine());
				for (int j = 0; j < M; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			int cnt = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (arr[i][j] == 1 && visited[i][j] == false) {
						cnt++;
						bfs(i, j);
					}
				}
			}
			System.out.println(cnt);
		}

	}

	public static void bfs(int x, int y) {

		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[]{x,y});

		while(!queue.isEmpty()) {
			int[] temp = queue.poll();

			for(int d=0;d<8;d++) {

				int dx = temp[0]+dir[d][0];
				int dy = temp[1]+dir[d][1];

				if(dx >= 0 && dx < N && dy >= 0 && dy < M && visited[dx][dy] == false && arr[dx][dy] == 1) {

					visited[dx][dy] = true;
					queue.offer(new int[]{dx, dy});

				}

			}

		}




	}

}

카운트를 두고 BFS가 수행된 횟수만 출력하면 되는 문제이다. 이미 방문한 섬인지 여부만 체크할 수 있다면 BFS로 풀수 있는 간단한 문제였다.