[백준] 그림 1926번 (c++)

출처 : 1926번: 그림 (acmicpc.net)

1926번: 그림

풀이 방법

bfs 문제로 맵 전체를 for 문을 돌며 board[y][x] 가 1이고 visited[y][x]가 -1 인 점을 bfs(y, x)를 호출하여 

그 점과 연결된 점들을 방문하여 넓이를 구하고 가장 큰 곳이면 답을 변수 ans에 저장한다.

그리고 bfs가 호출 될 때마다 그림의 개수 카운터를 증가시킨 후 출력한다.

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

int n, m, ans = 0, cnt = 0;
int board[501][501];
int visited[501][501];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void bfs(int y,int x) {
    int wd = 1;
    queue<pair<int, int>> q;
    visited[y][x] = 1;
    q.push(make_pair(y, x));
    while(!q.empty()) {
        int yy = q.front().first;
        int xx = q.front().second;
        q.pop();
        for (int i = 0;i < 4;i++) {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
            if (ny >= 0 && ny < n && nx >= 0 && nx < m && board[ny][nx] == 1) {
                if (visited[ny][nx] == -1) {
                    visited[ny][nx] = 1;
                    q.push(make_pair(ny, nx));                    
                    wd++;
                }
            }
        }
    }
    ans = max(ans, wd);
}

int main() {
    cin >> n >> m;
    memset(visited, -1 ,sizeof(visited));
    for (int i = 0;i < n;i++) {
        for (int k = 0;k < m;k++) {
            cin >> board[i][k];
        }
    }
    for (int i = 0;i < n;i++) {
        for (int k = 0;k < m;k++) {
            if (board[i][k] == 1) {
                if (visited[i][k] == -1) {
                    cnt++;
                    bfs(i, k);
                }
            }
        }
    }
    cout << cnt << endl << ans;
}