728x90
반응형
https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
#include <iostream>
#include <queue>
using namespace std;
int map[51][51];
int w, h;
int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1};
void bfs(int a, int b) {
map[a][b] = 0;
queue<pair<int, int>> q;
q.push(pair<int, int>(a, b));
int cx, cy, ax, ay;
while (!q.empty()) {
cx = q.front().first;
cy = q.front().second;
q.pop();
for (int i = 0; i < 8; i++) {
ax = cx + dx[i];
ay = cy + dy[i];
if (ax >= 0 && ay >= 0 && ax < h && ay < w && map[ax][ay] == 1) {
map[ax][ay] = 0;
q.push(pair<int, int>(ax, ay));
}
}
}
}
int main() {
int cnt;
cin >> w >> h;
while (w != 0 && h != 0) {
cnt = 0;
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) {
bfs(i, j);
cnt++;
}
}
}
cout << cnt << endl;
// map 초기화
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
map[i][j] = 0;
}
}
cin >> w >> h;
}
return 0;
}
1012번과 비슷한 문제로, BFS를 이용해서 풀었다.
728x90
반응형
'Algorithm > BAEKJOON' 카테고리의 다른 글
[BOJ] 12865번 평범한 배낭 (C++) (0) | 2021.11.05 |
---|---|
[BOJ] 1966번 프린터 큐 (C++) (0) | 2021.11.03 |
[BOJ] 1012번 유기농 배추 (C++) (0) | 2021.11.02 |
[BOJ] 10867번 중복 빼고 정렬하기 (C++) (0) | 2021.11.02 |
[BOJ] 1260번 DFS와 BFS (C++) (0) | 2021.11.01 |