백준 1926 그림 / C++

문제 : 링크텍스트

풀이 point

bfs를 통한 탐색을 진행
for문을 통해 1의 위치를 찾고 바로 bfs를 진행
1의 위치를 찾았다면 그림이 하나 있는 것이므로 ++그림, bfs는 한 그림에서만 진행되므로 bfs가 진행되면서 계속 ++면적을 해줌.

풀이 순서

1. 입력
2. 1의 위치를 찾고 bfs 진행
3. 면적을 가장 최댓값으로 갱신해나감
4. 면적과 그림의 갯수를 출력

코드

#include <iostream>
#include <vector>
#include <queue>

#define x first
#define y second

std::queue<std::pair<int,int>> Q;

std::vector <int> dx = {-1, 0, 1, 0};
std::vector <int> dy = {0, 1, 0, -1};

int grid[500][500];
int n, m;
int max{0};

void bfs(int i, int j){
    int area{1}; 
    grid[i][j] = 0;
    Q.push({i, j});
    while(!Q.empty()){
        auto cur = Q.front(); Q.pop();
        for(int k{0}; k<4; ++k){
            int nx = dx[k] + cur.x;
            int ny = dy[k] + cur.y;
            if(nx >= n || nx < 0 || ny >= m || ny < 0) continue;
            if(grid[nx][ny] == 0) continue;
            Q.push({nx, ny});
            grid[nx][ny] = 0;
            ++area;
        }
    }
    max = std::max(area, max);
}

int main(){
    int num{0};
    std::cin >> n >> m;
    for(int i{0}; i<n; ++i){
        for(int j{0}; j<m; ++j){
            std::cin >> grid[i][j];
        }
    }

    for(int i{0}; i<n; ++i){
        for(int j{0}; j<m; ++j){
            if(grid[i][j] == 1){
                ++num;
                bfs(i, j);
            }
        }
    }

    std::cout << num << '\n' << max;
    
    return 0;
}

2025-01-06T03:53:28.721Z