백준 4963번 : 섬의 개수 (C++)

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

4963번: 섬의 개수

 

 

코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int sum[50][50];
int map[50][50];
int dx[]={-1,1,0,0,-1,1,1,-1};  
int dy[]={0,0,-1,1,1,1,-1,-1};
 
int main() {
    int w,h;
    while(cin>>w>>h)
    {
        if(w==0 && h==0) break;
        memset(sum,0,sizeof(sum));
        queue<pair<int,int>> q;
        for(int i=0;i<h;i++)
        {
          for(int j=0;j<w;j++)
          {
              cin>>map[i][j];
          }
        }
        int sumnum=0;
        for(int i=0;i<h;i++)
        {
          for(int j=0;j<w;j++)
          {
              if(map[i][j]==1 && sum[i][j]==0)
              {
                  q.push({i,j});
                  sumnum++;
                  sum[i][j]=sumnum;
                  while(!q.empty())
                  {
                      int x=q.front().first;
                      int y=q.front().second; q.pop();
                      for(int i=0;i<8;i++)
                      {
                          if(x+dx[i]>=0 && x+dx[i]<h && y+dy[i]>=0 && y+dy[i]<w && map[x+dx[i]][y+dy[i]]==1 && sum[x+dx[i]][y+dy[i]]==0)
                          {
                              sum[x+dx[i]][y+dy[i]]=sumnum;
                              q.push({x+dx[i],y+dy[i]});
                          }
                      }
                  }
              }
          }
        }
       cout<<sumnum<<"\n";
        
    }
    return 0;
}

풀이

 각 테스트케이스마다 너비 w와 높이 h가 주어지고 w와 h만큼의 0과 1로 이루어진 지도가 주어질 때 섬의 개수를 출력하는 문제이다. 섬은 가로, 세로, 대각선으로 연결된 경우 하나의 섬이다. BFS를 이용해서 문제를 해결했다.

 먼저 17~28행에서 map 배열에 지도의 정보를 입력받는다. 25행부터 BFS를 이용하여 섬의 개수를 구하는 코드인데 map 배열의 모든 값을 검사한 뒤 map 배열의 값은 1인데 sum 배열의 값은 초깃값 그대로인 0 인경우 (29행) pair형으로 선언해놓은 큐에 행과 열의 값을 넣어주고 sum 배열에 섬의 번호를 넣는다. 섬의 번호는 map 배열의 값은 1인데 sum 배열의 값은 0인 경우를 발견할 때마다(새로운 섬을 발견할 때마다) 1씩 증가한다. 그 후에 34행의 while 문으로 BFS를 수행하는데 38행의 8번의 for 문으로 상, 하, 좌, 우, 대각선을 검사하면서 배열의 크기를 넘어가지 않으면서 map이 1이고 sum이 0 값인 위치를 찾으면 그 위치는 섬의 일부이므로 sum 배열에 섬의 번호를 넣어주고 큐에 행과 열의 값을 넣어준다. 위의 모든 반복문을 수행한 뒤의 sumnum 변수의 값이 섬의 개수가 된다.