[C++] 백준 문제풀이 (BFS) 4963번 섬의 개수

 

 

 

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

 

 

#include <bits/stdc++.h>

int w, h;
int cnt;
int map[50][50];
const int dy[] = {0, -1, -1, -1, 0, 1, 1, 1};
const int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};

void bfs(){
    bool visited[50][50] = {0, };
    cnt = 0;
    for (int i = 0; i < h; ++i){
        for (int j = 0; j < w; ++j){
            if (map[i][j] == 0 || visited[i][j]) continue;
            ++cnt;
            std::queue<std::pair<int, int>> q;
            q.push({i, j});
            visited[i][j] = true;

            while(!q.empty()){
                auto [y, x] = q.front(); q.pop();
                for (int dir = 0; dir < 8; ++dir){
                    int ny = y + dy[dir], nx = x + dx[dir];
                    if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
                    if (map[ny][nx] == 0 || visited[ny][nx]) continue;
                    q.push({ny, nx});
                    visited[ny][nx] = true;
                }
            }
        }
    }
}


int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    while(true){
        std::cin >> w >> h;
        if (w == 0 && h == 0) break;
        for (int i = 0; i < h; ++i){
            for (int j = 0; j < w; ++j){
                std::cin >> map[i][j];
            }
        }
        bfs();
        std::cout << cnt << "\n";
    }
    return 0;
}