백준 1926번: 그림 C++코드(BFS)

#include<iostream>
#include<queue>
#include<utility>
#include<vector>
#include<algorithm>

using namespace std;

int n,m;

int picture[501][501];
int visit[501][501] = {0,};
int x[4] = {0,0,1,-1};
int y[4] = {1,-1,0,0};

int bfs(int s1, int s2){
    int funcnt = 0;
    queue <pair <int,int> > q;
    q.push(make_pair(s1,s2));
    while(!q.empty()){
        funcnt += 1;
        pair <int,int> now = q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int py = now.first + y[i];
            int px = now.second + x[i];
            if(0<= py & py < n & 0<= px & px < m & visit[py][px] == 0 & picture[py][px] == 1){
                visit[py][px] = 1;
                q.push(make_pair(py,px));
            }
        }
    }
    return funcnt;
}

int main(){
    int cnt = 0;
    cin >> n >> m;
    vector <int> v;
    v.push_back(0);
    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(picture[i][j] == 1 & visit[i][j] == 0){
                visit[i][j] = 1;
                v.push_back(bfs(i,j));
                cnt += 1;
            }
        }
    }
    cout << cnt << endl;
    cout << *max_element(v.begin(),v.end());

}

설명

간단한 bfs문제이다. 다만 bfs함수 안에서 계속 그림의 방문한 1을 0으로 바꿔주고, 그림을 검사하면서 1이 나올때마다 bfs함수를 호출해 주면 된다. 단지번호 문제와 유사한 점이 있다.

 

문제점

visit 설정을 잘못해서 애를 먹었으나 금방 수정하였다.