[C++] 백준 문제풀이 (BFS) 1926번 그림

 

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

1926번: 그림

 

 

#include <bits/stdc++.h>

int n, m;
int map[500][500];
bool visit[500][500];
int cnt;
int maxArea;

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

int getArea(int r, int c){
    std::queue<std::pair<int, int >> q;
    q.push({r, c});
    visit[r][c] = true;
    int area = 1;

    while(!q.empty()){
        auto [y, x] = q.front(); q.pop();
        for (int dir = 0; dir < 4; ++dir){
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            if (map[ny][nx] == 0 || visit[ny][nx]) continue;
            q.push({ny, nx});
            visit[ny][nx] = true;
            ++area;
        }
    }
    return area;
}

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

    for (int y = 0; y < n; ++y){
        for (int x = 0; x < m; ++x){
            std::cin >> map[y][x];
        }
    }

    for (int y = 0; y < n; ++y){
        for (int x = 0; x < m; ++x){
            if (map[y][x] == 1 && !visit[y][x]){
                ++cnt;
                int area = getArea(y, x);
                maxArea = std::max(maxArea, area);
            }
        }
    }
    std::cout << cnt << "\n" << maxArea << "\n";
    return 0;
}