728x90
https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
// 코드
|
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
|
import java.util.*;
import java.io.*;
public class Main{
// 상, 하, 좌, 우
static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 대각선 : 좌-상, 좌-하, 우-상, 우-하
static int[][] dir2 = {{-1, -1}, {1, -1}, {-1, 1}, {1, 1}};
// 너비, 높이 값
static int w, h;
// 2차워 배열
static int[][] myArr;
// 방문기록
static int[][] visited;
// 탐색
static void bfs(int row, int col) {
Deque<int[]> deq = new ArrayDeque<>();
deq.add(new int[]{row, col});
visited[row][col] = 1;
while(!deq.isEmpty()) {
int[] getV = deq.pop();
for(int i=0; i<4; i++) {
// 상, 하, 좌, 우
int ny = dir[i][0] + getV[0];
int nx = dir[i][1] + getV[1];
if((0 <= ny && ny < h) && (0 <= nx && nx < w) && (visited[ny][nx] == 0) && (myArr[ny][nx] == 1)) {
visited[ny][nx] = 1;
deq.add(new int[]{ny, nx});
}
// 대각선
ny = dir2[i][0] + getV[0];
nx = dir2[i][1] + getV[1];
if((0 <= ny && ny < h) && (0 <= nx && nx < w) && (visited[ny][nx] == 0) && (myArr[ny][nx] == 1)) {
visited[ny][nx] = 1;
deq.add(new int[]{ny, nx});
}
}
}
}
// main
public static void main(String[] args) throws Exception {
StringBuilder sb = new StringBuilder();
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true) {
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
if(w == 0 && h == 0) break;
myArr = new int[h][w];
visited = new int[h][w];
for(int i=0; i<h; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<w; j++) {
myArr[i][j] = Integer.parseInt(st.nextToken());
}
}
int cnt = 0;
for(int i=0; i<h; i++) {
for(int j=0; j<w; j++) {
if(visited[i][j] == 0 && myArr[i][j] == 1) {
bfs(i, j);
cnt++;
}
}
}
sb.append(cnt + "\n");
}
bw.write(sb.toString());
br.close();
bw.flush();
bw.close();
}
}
|
cs |
반응형