코딩공작소
[백준]섬의개수 본문
https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는
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
|
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int w, h;
int map[50][50];
bool isV[50][50];
int dr[] = { 0,0,-1,1,-1,-1,1,1 }, dc[] = { 1,-1,0,0,-1,1,-1,1 };
int ans = 0;
void dfs(int r, int c) {
isV[r][c] = true;
for (int i = 0; i < 8; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nc < 0 || nr >= h || nc >= w) continue;
if (!isV[nr][nc] && map[nr][nc]) dfs(nr, nc);
}
}
void solve() {
ans = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (!isV[i][j] && map[i][j]) {
ans++;
dfs(i, j);
}
}
}
printf("%d\n", ans);
}
int main()
{
while (1) {
memset(map, 0, sizeof(map));
memset(isV, false, sizeof(isV));
cin >> w >> h;
if (w == 0 && h == 0) break;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> map[i][j];
}
}
solve();
}
return 0;
}
|
cs |
'알고리즘 > 그래프' 카테고리의 다른 글
| [백준]두동전 (0) | 2019.09.17 |
|---|---|
| [백준]PuyoPuyo (0) | 2019.09.15 |
| [백준]다리만들기 (0) | 2019.09.14 |
| [백준]단지번호붙이기 (0) | 2019.09.14 |
| 섬번호매기기 (0) | 2019.09.13 |