boj)4963 - 섬의 개수
2020. 11. 3. 14:37ㆍPS/boj
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
import java.io.*;
import java.util.*;
public class boj_4963 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static Queue<int[]> q = new LinkedList<>();
static int[][] map;
static boolean[][] v;
static int[] dx = { 0, 0, 1, -1, 1, -1, -1, 1 };
static int[] dy = { 1, -1, 0, 0, 1, 1, -1, -1 };
static int row, col, nx, ny;
static boolean isEnd;
public static void main(String[] args) throws IOException {
input();
bw.flush();
bw.close();
}
static void input() throws IOException {
if (!isEnd) {
st = new StringTokenizer(br.readLine());
col = Integer.parseInt(st.nextToken());
row = Integer.parseInt(st.nextToken());
if (col == 0 && row == 0) {
isEnd = true;
return;
}
map = new int[row][col];
v = new boolean[row][col];
for (int i = 0; i < row; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < col; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
solve();
input();
}
}
static void solve() throws IOException {
int ans = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (!v[i][j] && map[i][j] == 1) {
bfs(i, j);
ans++;
}
}
}
bw.write(ans + "\n");
}
static void bfs(int x, int y) {
v[x][y] = true;
q.offer(new int[] {x, y});
while (!q.isEmpty()) {
int[] now = q.poll();
for (int i = 0; i < 8; i++) {
nx = now[0] + dx[i];
ny = now[1] + dy[i];
if (nx < 0 || nx >= row || ny < 0 || ny >= col) continue;
if (map[nx][ny] == 1 && !v[nx][ny]) {
v[nx][ny] = true;
q.offer(new int[] {nx, ny});
}
}
}
}
}
|
cs |
- 대각선도 같은 섬으로 포함하기 때문에 8방향으로 탐색을 해줘야함
'PS > boj' 카테고리의 다른 글
boj)11719 - 그대로 출력하기 2 (0) | 2020.11.05 |
---|---|
boj)11721 - 열 개씩 끊어 출력하기 (0) | 2020.11.05 |
boj)1707 - 이분그래프 (0) | 2020.11.03 |
boj)11724 - 연결 요소의 개수 (0) | 2020.11.02 |
boj)5014 - 스타트링크 (0) | 2020.11.02 |