섬의 개수(BOJ4943)

문제

이미지 클릭

문제 설명

• 섬의 정의는 상하좌우 대각선 8방향과 인접한 땅이 있다면 그 부분을 하나의 섬으로 본다.
• 이렇게 섬을 나누었을 때 개수를 구하시오.

문제 풀이

• bfs를 활용하여서 방문 처리가 안 된 부분을 확인해 주면서 섬 하나에 포함되는 땅들을 방문 처리해 준다.
• 섬 하나를 방문 처리 해준 다음에 +1씩 카운트해준다.

최종 코드

#include<bits/stdc++.h>
using namespace std;
const int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,1,0,-1,1,-1,1,-1};
int n,m;
int main(){
      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
      while(true){
            cin>>m>>n;
            if(n==0&&m==0) return 0;
            vector<vector<int>> v(n+4, vector<int>(m+4)),visited(n+4,vector<int>(m+4,0));
            for(int i=1;i<=n;i++){
                  for(int j=1;j<=m;j++){
                        cin>>v[i][j];
                  }
            }
            int cnt=0; #섬의 개수
            for(int i=1;i<=n;i++){
                  for(int j=1;j<=m;j++){
                        if(v[i][j]&&!visited[i][j]){ 
                              cnt+=1;
                              visited[i][j]=1; #현제 위치 방문처리
                              queue<pair<int,int>> q; #현제 위치부터 bfs탐색
                              q.push({i,j});
                              while(!q.empty()){ #bfs탐색
                                    int x=q.front().first, y=q.front().second;
                                    q.pop();
                                    for(int k=0;k<8;k++){ #상하좌우 대각선 탐색
                                          int xx=x+dx[k],yy=y+dy[k];
                                          if(xx<1||yy<1||xx>n||yy>m||visited[xx][yy]||!v[xx][yy]) continue;
                                          #만약 범위를 벗어나거나 방문처리 되어있거나 바다인 경우에는 continue
                                          visited[xx][yy]=1;
                                          q.push({xx,yy});
                                    }
                              }
                        }
                  }
            }
            cout<<cnt<<"\n";
      }
}

이미지 클릭