[백준] 14716번 현수막

문제: 14716번: 현수막

#include <bits/stdc++.h>

using namespace std;

int cnt = 0;
vector<vector<int>> table;
vector<vector<bool>> visits;

int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[8] = {0, -1, 0, 1, -1, 1, -1, 1};

int m, n; // 현수막 크기

void BFS(int x, int y) {
    cnt++;
    
    queue<pair<int, int>> nexts;
    nexts.push({x, y});
    visits[x][y] = true; // 방문 표시
    
    while (!nexts.empty()) {
        pair<int, int> cur = nexts.front(); nexts.pop();

        for (int i=0; i<8; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (visits[nx][ny] == true || table[nx][ny] == 0) continue;

            nexts.push({nx, ny});
            visits[nx][ny] = true; // 방문 표시
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> n;
    table = vector<vector<int>>(m);
    visits = vector<vector<bool>>(m);
    for (int i=0; i<m; i++) {
        table[i] = vector<int>(n);
        visits[i] = vector<bool>(n);

        for (int j=0; j<n; j++) {
            cin >> table[i][j];
        }
    }
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            if (visits[i][j] == true) continue;
            if (table[i][j] == 0) continue;
            BFS(i, j);
        }
    }
    cout << cnt << "\n";
    
    return 0;
}