[BOJ] 4963번 섬의 개수

#include < iostream>
#include < queue>
#include < vector>
#include < cstring>


using namespace std;

int dy[8] = {-1,-1,-1,0,0,1,1,1};
int dx[8] = {-1,0,1,-1,1,-1,0,1};

int board[50][50];
bool check[50][50];

//w너비,h높이
int w,h;

void bfs(int y,int x){
    queue<pair<int,int>> q;
    check[y][x] = true;
    q.push(make_pair(y,x));

    while(!q.empty()){
        y=q.front().first;
        x=q.front().second;
        q.pop();

        for(int dir=0;dir<8;dir++){
            int ny = y + dy[dir];
            int nx = x + dx[dir];

            if(ny<0 || nx<0 || ny>=h || nx>=w)
                continue;

            if(check[ny][nx] == false && board[ny][nx] == 1){
                check[ny][nx] = true;
                q.push(make_pair(ny,nx));
            }
        }
    }

}

int main()
{


    while(1){
        cin>>w>>h;
        if(w==0 && h==0)
            break;

        //2차원 배열 board,check 초기화
        memset(board,0,sizeof(board));
        memset(check,false,sizeof(check));

        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                cin>>board[i][j];
            }
        }

        //입력 확인
        /*for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                cout<<board[i][j]<<" ";
            }
            cout<<endl;
        }*/
        int count=0;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(board[i][j] == 1 && check[i][j] == false){
                    bfs(i,j);
                    count++;
                }
            }
        }

        cout<<count<<endl;

    }

    return 0;
}

 

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수