4963번 섬의 개수

 BFS 기본 문제. 

 

 

#include <iostream>
#include <vector>
#include <queue>
#define visited true
#define Non_visited false
#define MAX 51
 
using namespace std;
 
typedef pair<int,int> pir;
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
int xx2[4]={1,-1,1,-1};
int yy2[4]={1,-1,-1,1};
int map[MAX][MAX];
bool flag;
int w,h;
vector<int> answer;
queue<pir> q;
bool check[MAX][MAX];
int cnt;
 
void bfs(){
    
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        
        check[x][y]=true;
        
        for(int i=0;i<4;i++){
            int nx = x + xx[i];
            int ny = y + yy[i];
            
            int nx2 = x + xx2[i];
            int ny2 = y + yy2[i];
            
            if(0<=nx && nx<h && 0<=ny && ny<w && !check[nx][ny] && map[nx][ny]==1){
                check[nx][ny]=true;
                q.push(pir(nx,ny));
            }
            
            if(0<=nx2 && nx2<h && 0<=ny2 && ny2<w && !check[nx2][ny2] && map[nx2][ny2]==1){
                check[nx2][ny2]=true;
                q.push(pir(nx2,ny2));
            }
 
        }
    }
}
void reset(int a, int b){
    cnt=0;
    for(int i=0;i<a;i++){
        for(int j=0;j<b;j++){
            check[i][j]=false;
        }
    }
}
 
int main(){
    while(!flag){
        cin >> w >> h;
        
        if(w==0 && h==0){
            break;
        }
        else{
            for(int i=0;i<h;i++){
                for(int j=0;j<w;j++){
                    cin >> map[i][j];
                }
            }
        }
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(!check[i][j] && map[i][j]==1){
                    q.push(pir(i,j));
                    bfs();
                    cnt++;
                }
            }
        }
        answer.push_back(cnt);
        reset(h,w);
    }
    
    for(int i=0;i<answer.size();i++){
        cout << answer[i] << endl;
    }
}