OJ
[BOJ] 4963 섬의 개수 (JAVA)
P3PP4
2023. 1. 19. 10:00
https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
1을 발견하면 BFS를 돌려봅시다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int N, M;
static int[][] map;
static boolean[][] visited;
static int[] dr = { -1, 0, 1, 0, -1, -1, 1, 1 };
static int[] dc = { 0, 1, 0, -1, -1, 1, -1, 1 };
public static void main(String[] args) throws Exception {
while(true) {
st = new StringTokenizer(br.readLine(), " ");
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
if(N == 0 && M == 0) break;
map = new int[N][M];
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
} // end of input
Queue<int[]> q = new LinkedList<>();
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if(map[i][j] == 1 && !visited[i][j]) {
q.offer(new int[] { i, j });
visited[i][j] = true;
cnt++;
while(!q.isEmpty()) {
int[] a = q.poll();
for (int dir = 0; dir < 8; dir++) {
int nr = a[0] + dr[dir];
int nc = a[1] + dc[dir];
if(0 <= nr && nr < N && 0 <= nc && nc < M && !visited[nr][nc] && map[nr][nc] == 1) {
q.offer(new int[] { nr, nc });
visited[nr][nc] = true;
}
}
}
}
}
}
sb.append(cnt).append("\n");
}
System.out.print(sb.toString());
}
}