//섬의 개수 DFS //출처O #include <iostream> #include <cstring> #include <queue> using namespace std; int map[50][50], visit[50][50]; int dx[8] = { 1,1,0,-1,-1,-1,0,1 }, dy[8] = { 0,1,1,1,0,-1,-1,-1 }; int w, h; void dfs(int y, int x) { for (int i = 0; i < 8; i++) { int nextX = x + dx[i]; int nextY = y + dy[i]; if (nextX < 0 || nextY < 0 || nextX >= w || nextY >= h)continue; if (!visit[nextY][nextX] && map[nextY][nextX]) { visit[nextY][nextX] = 1; dfs(nextY, nextX); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); while (1) { int cnt = 0; cin >> w >> h; if (!w && !h)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 (!visit[i][j] && map[i][j]) { visit[i][j] = 1; dfs(i, j); cnt++; } } } cout << cnt << "\n"; memset(visit, 0, sizeof(visit)); } }
반응형
'알고리즘' 카테고리의 다른 글
[알고리즘 C++] 백준 2655 - 가장높은탑쌓기 (0) | 2021.12.17 |
---|---|
[알고리즘 C++] 프로그래머스 - 등굣길 (0) | 2021.12.17 |
[알고리즘 C++] Linked List & Vector (0) | 2021.12.17 |
[알고리즘 C++] 백준 1912 - 연속합 (0) | 2021.12.17 |
[알고리즘 C++] 백준 14496 - 그대, 그머가 되어 (0) | 2021.12.17 |