[백준] 1926 그림

 

풀이

#include <bits/stdc++.h>
using namespace std;

int board[502][502];
bool vis[502][502];

int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
        }
    }

    int num = 0;
    int mx = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vis[i][j] || board[i][j] == 0) continue;
            num++;
            queue<pair<int, int>> q;
            vis[i][j] = 1;
            q.push({i,j});
            int area = 0;
            while (!q.empty()) {
                area++;
                pair<int,int> cur = q.front(); q.pop();
                for (int dir = 0; dir < 4; dir++) {
                    int nx = cur.first + dx[dir];
                    int ny = cur.second + dy[dir];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                    if (vis[nx][ny] || board[nx][ny] == 0) continue;
                    vis[nx][ny] = 1;
                    q.push({nx,ny});
                }
            }
            mx = max(mx, area);
        }
    }

    cout << num << "\n" << mx;

    return 0;
}

 

BFS의 기본적인 문제중 하나이다.

2차원 배열에서 그림(1로 이루어진 덩어리)가 몇개 있는지, 그림 중 가장 넓은 그림(칸 수가 가장 큰 그림)의 넓이를 구하면된다.

 

그림이 몇개가 있는지를 구하는법은 단순히 `pop()`을 할때마다 카운트를 증가시켜 구하면되고, 그림 중 가장 넓은 그림의 넓이를 구하기 위해서 이중 반복문을 돌며 배열의 칸의 위치를 옮겨가며 BFS를 돌지않은 새로운 그림이 나타나면 그 그림의 위치에서 BFS를 돌며 그림의 넓이를 측정하여(칸 수) 최종적으로 어떤 값이 가장 큰 값인지를 구하여 풀면된다.