[4963번] 섬의 개수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

BFS를 통해 문제를 해결할 수 있다. 모

모든 좌표를 돌며 이미 방문한 점이면 방문하지 않고 그 외에는 BFS를 돌며 BFS가 돌았던 총 횟수가 정답이 된다.

이때 8방향으로 BFS를 돈다는 것이 일반적인 BFS와 차이점이다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

#include <iostream> #include <cstdio> #include <queue> #include <memory.h>   using namespace std;   typedef pair<int, int> pii;   int arr[52][52]; bool visit[52][52];   int dy[8] = { -1,0,1,0, -1, -1, 1, 1 }; int dx[8] = { 0,-1,0,1, -1, 1, -1, 1 };   int main() {     while (1)     {         int m, n;         scanf("%d %d", &m, &n);           if (m == 0 && n == 0)             break;           memset(arr, 0, sizeof(arr));         memset(visit, 0, sizeof(visit));           for (int i = 0; i < n; i++)             for (int j = 0; j < m; j++)                 scanf("%d", &arr[i][j]);           int cnt = 0;         for(int i = 0 ; i < n; i ++)             for (int j = 0; j < m; j++)             {                 queue<pii> q;                 if (arr[i][j] == 1 && !visit[i][j])                 {                     cnt++;                     q.push({ i,j });                       while (!q.empty())                     {                         int y = q.front().first;                         int x = q.front().second;                         q.pop();                           if (visit[y][x])                             continue;                           visit[y][x] = true;                           for (int k = 0; k < 8; k++)                         {                             int ny = y + dy[k];                             int nx = x + dx[k];                                                          if ((0 <= ny && ny < n) && (0 <= nx && nx < m) && arr[ny][nx] == 1)                                 q.push({ ny,nx });                         }                     }                 }               }           printf("%d\n", cnt);     }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus