(C++) - 백준(BOJ) 1926번 : 그림

www.acmicpc.net/problem/1926

1926번: 그림

 

bfs문제였습니다.

 

풀이방법

인접한 그림들은 모두 그림 하나의 일부입니다. 

 

 방문하지 않은 곳, 그림이 칠해져있는(1인) 곳에 대해 bfs를 실행합니다. 이 때, bfs가 호출되는 수가 곧 영역의 개수가 됩니다. 또한 bfs함수가 호출된 후 실행시 한 영역에 대해 1의 개수를 센 후 반환합니다. 이 때 반환값이 곧 한 영역의 그림 넓이가 됩니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int picture[501][501];
int visited[501][501];
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
int areaCnt, maxArea;
int n,m;

int bfs(int i, int j){
    queue <pii> q;
    visited[i][j] = 1;
    q.push({i,j});
    int area = 1;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= n || 0 > ny || ny >= m) continue;
            if(visited[nx][ny] || !picture[nx][ny]) continue;
            visited[nx][ny] = 1;
            area++;
            q.push({nx,ny});
        }
    }
    return area;
}

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

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(!visited[i][j] && picture[i][j]){
                areaCnt++;
                maxArea = max(maxArea,bfs(i,j));
            }
        }
    }

    cout << areaCnt << '\n';
    cout << maxArea << '\n';
}