백준 s1 1926 그림 c++

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

 

풀이

 

for (모든 좌표 i, j)

  if board가 1이고, vis 방문하지 않았다면

    mx = max(mx, bfs로 나온 그림 크기)

    answer++;

 

실수했던 것

 

그림이 아무 것도 없을 때 max값이 0이 나와야 하는데 습관적으로 max = -1로 두어서 틀렸음

역시 틀린 게 있을 땐 문제를 다시 읽어보는 게 중요

 

/*boj s1 1926 그림*/
#include <iostream>
#include <queue>
#define MAXN 502
using namespace std;

int N, M;
int board[MAXN][MAXN];
int vis[MAXN][MAXN];
int answer = 0;
int mx = 0;

int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };
int bfs(int x, int y)
{
    queue<pair<int, int>> Q;
    int area = 0;
    vis[x][y] = 1;
    Q.push({ x, y });

    while (!Q.empty()) {
        pair<int, int> cur = Q.front();
        Q.pop();
        area++;

        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 (board[nx][ny] == 0)
                continue;
            if (vis[nx][ny] > 0)
                continue;

            vis[nx][ny] = 1;
            Q.push({ nx, ny });
        }
    }

    return area;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;

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

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 1 && vis[i][j] == 0) {
                mx = max(mx, bfs(i, j));
                answer++;
            }
        }
    }

    cout << answer << "\n"
         << mx << "\n";
}