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로 풀수 있는 간단한 문제였다.