촌수 계산(2644)
풀이
알고리즘 과목 수강할때 비슷한 문제를 풀어봐서 금방 해결하였다.
육지이고 방문하지 않은 위치를 기준으로 bfs를 하는데 상, 하, 좌, 우, 대각선을 전부 확인하면 된다.
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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 FastScanner {
BufferedReader br;
StringTokenizer st;
public FastScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
}
class Point {
int w;
int h;
public Point(int w,int h) {
this.w = w;
this.h = h;
}
public int getW() {
return this.w;
}
public int getH() {
return this.h;
}
}
public class Main {
static int arr[][];
static boolean visited[][];
static int dx[] = {0, 0 ,-1, 1, -1, 1, -1, 1}; // 상, 하, 좌, 우, 상좌, 상우, 하좌, 하우
static int dy[] = {-1, 1, 0, 0, -1, -1, 1, 1 };
public static void main(String args[]) throws IOException {
FastScanner sc = new FastScanner();
while(true) {
int w = sc.nextInt(); // 가로
int h = sc.nextInt(); // 세로
int cnt = 0;
if(w == 0 && h == 0) break;
arr = new int[h][w];
visited = new boolean[h][w];
for(int i=0; i<h; i++)
for(int j=0; j<w; j++)
arr[i][j] = sc.nextInt();
for(int i=0; i<h; i++) {
for (int j = 0; j < w; j++) {
if(arr[i][j] == 1 && !visited[i][j]) {
visited[i][j] = true;
bfs(new Point(j,i), w, h);
cnt ++;
}
}
}
System.out.println(cnt);
}
}
public static void bfs(Point p, int w, int h) {
Queue<Point> queue = new LinkedList<>();
queue.add(p);
while(!queue.isEmpty()){
Point tmp = queue.poll();
int curW = tmp.getW();
int curH = tmp.getH();
for(int i=0; i<8; i++){
int nextW = curW + dx[i];
int nextH = curH + dy[i];
if(nextW >=0 && nextW < w && nextH >=0 && nextH < h){
if(arr[nextH][nextW] == 1 && !visited[nextH][nextW]){
visited[nextH][nextW] = true;
queue.add(new Point(nextW,nextH));
}
}
}
}
}
}