그림 (feat. 백준, 1926번)

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

1926번: 그림

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, dx[4], dy[4], arr[500][500];
bool visit[500][500];
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[0] = 1, dx[1] = -1, dx[2] = dx[3] = 0;
    dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
    cin >> N >> M;
    for(register int n = 0, m; n < N; ++n)
        for(m = 0; m < M; ++m)
            cin >> arr[n][m], visit[n][m] = false;
    register int ans1 = 0, ans2 = 0;
    queue<pair<int, int>> q;
    for(register int n = 0, m; n < N; ++n)
        for(m = 0; m < M; ++m)
            if(arr[n][m] == 1 && !visit[n][m]){
                register int cnt = 1;
                ++ans1;
                q.push(make_pair(n, m));
                visit[n][m] = true;
                while(!q.empty()){
                    auto p = q.front(); q.pop();
                    auto x = p.first, y = p.second;
                    for(register int d = 0, nx, ny; d < 4; ++d){
                        nx = x + dx[d], ny = y + dy[d];
                        if(0 <= nx && nx < N && 0 <= ny && ny < M && arr[nx][ny] == 1 && !visit[nx][ny])
                            visit[nx][ny] = true, ++cnt, q.push(make_pair(nx, ny));
                    }
                }
                ans2 = max(ans2, cnt);
            }
    cout << ans1 << "\n" << ans2;
    return 0;
}
// *&)*@*

 

반응형

1. 전형적인 bfs 유형입니다.
2. 1이고 방문하지 않은 경우, 해당 지점부터 상,하,좌,우 가 방문하지 않았고 1인지를 확인합니다. 그 개수를 카운팅한다면 그림의 넓이이고 2번 조건인 경우 그림의 개수가 증가합니다.