[백준 4963번] 섬의 개수

문제 링크:https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

<문제 풀이> BFS

8방향 BFS를 돌리고 큐가 빌 때마다 섬의 개수를 카운트하면 됩니다.

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first 
#define Y second 
 
int w, h;
int board[50][50];
bool visited[50][50];
 
int dx[8] = {0 ,-1, -1, -1, 0, 1, 1, 1};
int dy[8] = { 1, 1, 0,-1,-1,-1, 0, 1};
 
int bfs() {
    queue<pair<int, int> > Q;
    int res = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (!visited[i][j] && board[i][j] == 1) {
                Q.push({ i, j });
                visited[i][j] = true;
                while (!Q.empty()) {
                    auto cur = Q.front(); Q.pop();
                    for (int dir = 0; dir < 8; dir++) {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if (nx < 0 || ny < 0 || nx >= h || ny >= w)continue;
                        if (board[nx][ny] == 0 || visited[nx][ny])continue;
                        Q.push({ nx, ny });
                        visited[nx][ny] = true;
                    }
                }
                res++;
            }
        }
    }
    return res;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  
    while (true) {
        cin >> w >> h;
        if (w == 0 && h == 0) break;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin>> board[i][j];
            }
        }
        cout << bfs()<< '\n';
        fill(&board[0][0], &board[49][50], 0);
        fill(&visited[0][0], &visited[49][50], 0);
    }
 
 
    return 0;
}