[BaekJoon] 1926번 : 그림

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• BFS를 활용하는 문제로 배열의 모든 지역에서 BFS를 실행합니다.
• 처음 BFS에서 실행하여 탐색하지 않은 지역에서 다시 BFS를 실행하여 그림의 갯수를 파악합니다.
• 그림의 최대 크기는 BFS를 실행하면서 큐에서 pop한 갯수를 세어 비교합니다.

#include<iostream>
#include<queue>
#include<utility>
using namespace std;

int n,m;
int arr[500][500];
bool visit[500][500];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

bool inside(int y,int x){
    return 0<=y && y<n && 0<=x && x<m;
}

int main(){
    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>>arr[i][j];
        }
    }
    int cnt = 0;
    int ans = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(arr[i][j] && !visit[i][j] ){
                cnt++;
                int total = 0;
                visit[i][j] = 1;
                
                queue<pair<int,int>> q;
                q.push({i,j});
                
                while(!q.empty()){
                    int y = q.front().first;
                    int x = q.front().second;
                    q.pop();
                    total++;
                    
                    for(int k=0;k<4;k++){
                        int dy = y + dir[k][0];
                        int dx = x+ dir[k][1];
                        
                        if(inside(dy,dx) && arr[dy][dx] && !visit[dy][dx]){
                            visit[dy][dx] = 1;
                            q.push({dy,dx});
                        }
                    }
                }
                ans = max(ans, total);
            }
        }
    }
    cout<<cnt<<"\n";
    cout<<ans<<"\n";
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.