[백준]4963. 섬의 개수

[문제]

 

www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

[풀이]

 

입력이 주어지면 섬의 개수를 구해서 출력하면 된다.

상,하,좌,우,대각선 방향으로 연결된 것은 하나의 섬으로 본다.

 

전형적인 BFS 문제로 섬의 개수로 방문 처리도 해주었다.

따라서 입력이 0과 1이므로 섬의 개수를 저장하는 cnt 변수를 2부터 시작하고 출력은 cnt-1로 해주었다.

 

BFS 경우 방문 처리를 꼭 해줘야된다.

방문처리를 하지 않으면 계속  queue에 담기게 되어 메모리,시간 초과가 발생한다.

 

[코드]

 

시간 : 0ms

 

#include <iostream>
#include <queue>
#define MAX 51

using namespace std;

struct pos{
    int x,y;
};

int N,M;
int map[MAX][MAX]={0,};

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

void BFS()
{
    queue <pos> q;
    int cnt =1;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            
            if(map[i][j]==1){
                cnt++;
                map[i][j] = cnt;
                q.push({i,j});
            }
            
            while(!q.empty()){
                int x = q.front().x;
                int y = q.front().y;
                q.pop();
                
                for(int k=0;k<8;k++){
                    
                    int nx= x+dx[k];
                    int ny= y+dy[k];
                    
                    if(nx<0||ny<0||nx>=N||ny>=M||map[nx][ny]!=1)  continue;
                    map[nx][ny]= cnt;
                    q.push({nx,ny});
                    
                }
            }
        }
    }
    
    printf("%d\n",cnt-1);
}

int main(void)
{
    
    while(1){
        scanf("%d %d",&M, &N);
        
        if(!N && !M)    break;
        
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++)    scanf("%d",&map[i][j]);
        }
        
        BFS();
    }
    
    return 0;
    
}