[C++] 백준 1926번: 그림

mx = max(mx, area); 오랜만에 푸니까 자꾸 까먹는데 꼭 기억해두자!

굉장히 쉬운 bfs 문제인듯하다.

빠르게 짜다가 dx dy를 자꾸 dx dx로 쓰는데 조심해서 짜자!

 

#include <iostream>
#include <queue>
#define X first
#define Y second
using namespace std;

int board[505][505];
int vis[505][505];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int n, m;

queue<pair<int, int>> Q;
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> board[i][j];
        }
    }
    int mx = 0;
    int num = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            
            if(board[i][j] == 1 && vis[i][j] == 0){
                num++;
                queue <pair<int, int>> Q;
                int area = 0;
                
                vis[i][j] = 1;
                Q.push({i, j});
                while(!Q.empty()){
                    area++;
                    auto cur = Q.front(); Q.pop();
                    for(int i = 0; i < 4; i++){
                        int nx = cur.X + dx[i];
                        int ny = cur.Y + dy[i];
                        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                        if(vis[nx][ny] == 1 || board[nx][ny] == 0) continue;

                        vis[nx][ny] = 1;
                        Q.push({nx, ny});
                    }
                }
                //if(mx <= area) mx = area;
                mx = max(mx, area)
            }
            
        }
    }
    
    cout << num << " " << mx;
    return 0;
}