728x90
문제 4963번
https://www.acmicpc.net/problem/4963
갈 수 있는 8가지 방향을 dy, dx로 나누어 저장해준다. while문을 이용해 입력받은 값에 대한 섬의 개수를 구해준다. map 배열에 입력받은 값들을 넣어주고, map에 섬이 있는 부분인데 방문을 안 한 부분이라면 dfs를 수행해준다. 그리고 count를 올려준다. 만약 입력받은 w와 h가 0이라면 반복문을 빠져나와준다.
#include <iostream>
using namespace std;
int dy[] = { 0,0,-1,1,-1,-1,1,1 };
int dx[] = { 1,-1,0,0,-1,1,-1,1 };
const int MAX = 50;
int w, h;
int map[MAX][MAX];
bool visited[MAX][MAX];
void reset() {
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
map[i][j] = 0;
visited[i][j] = 0;
}
}
}
void DFS(int x, int y) {
visited[x][y] = true;
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
continue;
}
if (map[nx][ny] == 1 && visited[nx][ny] == 0) {
DFS(nx, ny);
}
}
}
int main() {
while (true) {
reset();
cin >> w >> h;
int count = 0;
if (w == 0 && h == 0) {
break;
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> map[i][j];
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (map[i][j] == 1 && visited[i][j] == 0) {
DFS(i, j);
count++;
}
}
}
cout << count << endl;
}
}
728x90
'백준 > C++' 카테고리의 다른 글
[C++] 백준 10871번 - X보다 작은 수 (0) | 2024.03.24 |
---|---|
[C++] 백준 10773번 - 제로 (2) | 2024.03.24 |
[C++] 백준 1697번 - 숨바꼭질 (2) | 2024.03.07 |
[C++] 백준 2178번 - 미로 탐색 (0) | 2024.03.07 |
[C++] 백준 2606번 - 바이러스 (3) | 2024.03.05 |