2667 - 단지번호붙이기
1. 개요
https://www.acmicpc.net/problem/2667
2. 코드
C++
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
#include <cstdio> // for scanf, printf
#include <algorithm> // for sort
using namespace std;
int n, arr[27][27], res[27*27], resCnt;
int dirs[][2] = {
{1, 0},
{-1, 0},
{0, 1},
{0, -1}
};
int findHomes(int r, int c) {
int sum = 1;
for (int i = 0; i < 4; i++) {
if (arr[r+dirs[i][0]][c+dirs[i][1]] == 1) {
arr[r+dirs[i][0]][c+dirs[i][1]] = 0;
sum += findHomes(r+dirs[i][0], c+dirs[i][1]);
}
}
return sum;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%1d", &arr[i][j]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (arr[i][j] == 1) {
arr[i][j] = 0;
res[resCnt++] = findHomes(i, j);
}
}
}
printf("%d\n", resCnt);
sort(res, res+resCnt);
for (int i = 0; i < resCnt; i++)
printf("%d\n", res[i]);
return 0;
}
3. 설명
- 주어진 배열을 전체 탐색
- 탐색 중 1이 나오면 DFS로 이어진 1을 탐색(재귀)
- 탐색 완료한 1은 0으로 변경
- 연결된 집을 모두 탐색하면 집의 크기를 +1 해서 return
4. 여정
- 제출 언어를 잘 봅시다.
- 성공