문제
Farmer John's cows have finally blasted off from earth and are now floating around space in their Moocraft. The cows want to reach their fiery kin on Jupiter's moon of Io, but to do this they must first navigate through the dangerous asteroid belt.
Bessie is piloting the craft through this treacherous N x N (1 <= N <= 1,000) sector of space. Asteroids in this sector comprise some number of 1 x 1 squares of space-rock connected along their edges (two squares sharing only a corner count as two distinct asteroids). Please help Bessie maneuver through the field by counting the number of distinct asteroids in the entire sector.
Consider the 10 x 10 space shown below on the left. The '*'s represent asteroid chunks, and each '.' represents a. vast void of empty space. The diagram on the right shows an arbitrary numbering applied to the asteroids.
...**..... ...11.....
.*........ .2........
......*... ......3...
...*..*... ...3..3...
..*****... ..33333...
...*...... ...3......
....***... ....444...
.*..***... .5..444...
.....*...* ......4...6
..*....... ..7........It's easy to see there are 7 asteroids in this sector.
입력
- Line 1: A single integer: N
- Lines 2..N+1: Line i+1 contains row i of the asteroid field: N characters
출력
- Line 1: A single integer indicating the number of asteroids in the field.
|
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
|
#include <stdio.h>
char map[1000][1002];
int dy[] = {-1, 1, 0, 0}, dx[] = {0, 0, -1, 1};
int n, cnt;
void dfs(int r, int c) {
map[r][c] = '.';
for (int i = 0; i < 4; i++) {
int y = r + dy[i], x = c + dx[i];
if (y < 0 || y >= n || x < 0 || x >= n)continue;
if (map[y][x] == '*')
dfs(y, x);
}
}
int main() {
scanf("%d", &n);
getchar();
for (int i = 0; i < n; i++)
fgets(map[i], 1002, stdin);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (map[i][j] == '*')
cnt++, dfs(i, j);
printf("%d\n", cnt);
return 0;
}
|
cs |
구역의 개수를 구하는 가장 기본적인 DFS 문제였다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 4920 테트리스 게임 (0) | 2020.12.14 |
|---|---|
| 백준 온라인 저지 1038 감소하는 수 (0) | 2020.12.09 |
| 백준 온라인 저지 2676 라스칼 삼각형 (0) | 2020.12.07 |
| 백준 온라인 저지 1406 에디터 (0) | 2020.12.07 |
| 백준 온라인 저지 18870 좌표 압축 (0) | 2020.12.02 |
