(BOJ) 1926 풀이

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int BFS(int x, int y);
int ar[502][502], visited[502][502];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
queue<pair<int, int>> Q;
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M, count = 0, max = 0;
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
            cin >> ar[i][j];
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (!visited[i][j] && ar[i][j])
            {
                int tmp = BFS(i, j);
                max = tmp > max ? tmp : max;
                count++;
                // cout << "(" << i << "," << j << ") : " << tmp << "\n";
            }
        }
    }
    cout << count << '\n'
         << max << '\n';
}
int BFS(int x, int y)
{
    visited[x][y] = 1;
    Q.push({x, y});
    int num = 1;
    while (!Q.empty())
    {
        pair<int, int> cur = Q.front();
        Q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = dx[i] + cur.X;
            int ny = dy[i] + cur.Y;
            if (nx < 1 || nx > 500 || ny < 1 || ny > 500 || visited[nx][ny] || !ar[nx][ny])
                continue;
            Q.push({nx, ny});
            visited[nx][ny] = 1;
            num++;
        }
    }
    return num;
}

전형적인 BFS 문제로, 강의에서 풀길래 한번 풀어봤다.

N*M 배열을 한 번씩 방문해서 방문하지 않았던 곳이고, 그림이 그려져 있으면 BFS 함수를 호출한다.

여기서는 num 값 1부터, 방문할 수 있는 곳을 queue 에 push 할 떄마다 num 값을 증가시켜

그림의 크기를 리턴한다.

main 함수 반복문에서는 붙어있지 않은 그림을 만날 때마다 (BFS 호출 가능할 때)

count 를 증가시키고, 리턴값으로 (그림의 크기) 최대값을 구한 뒤, 마지막에 출력한다.

그림이 하나도 없을 경우에는 0으로 설정해야하는데, 기본값을 -1 로 줘서 53% 에서 틀렸었다.