4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
코드 설명
BFS + visited배열을 이용하여 탐색하였다. 보통 4방향인데 대각선도 포함이므로 8방향으로 탐색하였다.
코드
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int N, M;
int map[51][51];
bool visited[51][51];
int dy[] = { 0,0,-1,-1,-1,1,1,1 };
int dx[] = { -1,1,-1,1,0,-1,1,0 };
int cnt;
vector<int> answer;
void bfs(int y, int x) {
queue<pair<int, int>> q;
visited[y][x] = true;
q.push({ y,x });
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
for (int i = 0; i < 8; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
if (!visited[ny][nx] && map[ny][nx]==1) {
q.push({ ny,nx });
visited[ny][nx] = true;
}
}
}
}
int main()
{
while (1) {
cin >> M >> N;
if (N == 0 && M == 0) break;
memset(map, 0, sizeof(map));
memset(visited, false, sizeof(visited));
cnt = 0;
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
cin >> map[y][x];
}
}
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
if (map[y][x] == 1 && !visited[y][x]) {
cnt++;
bfs(y, x);
}
}
}
answer.push_back(cnt);
}
for (int i = 0; i < answer.size(); i++) {
cout << answer[i] << endl;
}
return 0;
}