728x90
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
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
|
import java.util.*;
import java.io.*;
public class Main{
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N;
static int[][] mainArr, checkArr;
static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
static int bfs(int row, int col) {
int result = 1;
Deque<int[]> deq = new ArrayDeque<>();
deq.add(new int[]{row, col});
checkArr[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<N) && (0<=nx && nx<N) && checkArr[ny][nx] == 0 && mainArr[ny][nx] != 0 ) {
checkArr[ny][nx] = 1;
deq.add(new int[]{ny, nx});
result++;
}
}
}
return result;
}
public static void main(String[] args) throws Exception {
// Please Enter Your Code Here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
mainArr = new int[N][N];
checkArr = new int[N][N];
for(int i=0; i<N; i++) {
int col = 0;
for(char ch : br.readLine().toCharArray()) {
mainArr[i][col++] = Integer.parseInt(String.valueOf(ch));
}
}
ArrayList<Integer> resArr = new ArrayList<>();
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(checkArr[i][j] == 0 && mainArr[i][j] == 1) {
int result = bfs(i, j);
if(result>0) resArr.add(result);
}
}
}
StringBuilder sb = new StringBuilder();
sb.append(resArr.size() + "\n");
Collections.sort(resArr);
for(int resNum : resArr) {
sb.append(resNum + "\n");
}
bw.write(sb.toString());
br.close();
bw.flush();
bw.close();
}
}
|
cs |
반응형