[アルゴリズム]伯準-4963(島の個数)/Java
21985 ワード
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Node {
int y, x;
public Node(int y, int x) {
this.y = y;
this.x = x;
}
}
public class Main {
static int width;//너비
static int height;//높이
static int map[][];
static int visited[][];
static int dx[] = {1, 0, -1, 0, -1, 1, 1, -1};
static int dy[] = {0, 1, 0, -1, -1, -1, 1, 1};
static Queue<Node> queue;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true) {
String input = br.readLine();
// 입력 끝
if(input.equals("0 0")) {
return;
}else {
StringTokenizer st = new StringTokenizer(input);
width = Integer.parseInt(st.nextToken());
height = Integer.parseInt(st.nextToken());
map = new int[height][width];
visited = new int[height][width];
for(int i=0; i<height; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<width; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int count=0;
queue = new LinkedList<>();
for(int i = 0 ; i < height ; i++) {
for(int j = 0 ; j < width ; j++) {
if(visited[i][j] == 0 && map[i][j]==1) {
bfs(i, j);
count++;
}
}
}
System.out.println(count);
}
}
}
public static void bfs(int y, int x) {
queue.add(new Node(y, x));
visited[y][x]=1;
while(!queue.isEmpty()) {
int cury = queue.peek().y;
int curx = queue.peek().x;
queue.poll();
for(int i=0; i<8; i++) {
int nextX = curx+dx[i];
int nextY = cury+dy[i];
if(nextX<0 || nextY<0 || nextY>=height || nextX>=width) {
continue;
}
if(visited[nextY][nextX] == 1) {
continue;
}
if(map[nextY][nextX]==1) {
queue.add(new Node(nextY, nextX));
visited[nextY][nextX]=1;
}
}
}
}
}
Reference
この問題について([アルゴリズム]伯準-4963(島の個数)/Java), 我々は、より多くの情報をここで見つけました https://velog.io/@cheal3/알고리즘-백준-4963-섬의-개수-자바テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol