[14716번] 현수막

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

기본적인 BFS를 이해하고 있다면 이 문제도 쉽게 해결이 가능하다.

위, 아래, 좌, 우, 왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래 8가지 방향으로 BFS 탐색을 해주면 된다.

이때 한번의 BFS에서 연속으로 탐색이 되면 그 값들은 모두 하나의 단어가 되는 것이고 visit 배열에서 true로 변경시키면 된다.

소스 코드 : 

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

#include <iostream> #include <cstdio> #include <queue>   using namespace std;   int arr[300][300]; bool visit[300][300];   int dy[8] = { 1,0,-1,0, -1, -1, 1, 1 }; int dx[8] = { 0,1,0,-1, -1, 1, -1, 1 };   int main() {     int n, m;     scanf("%d %d", &n, &m);       for (int i = 0; i < n; i++)         for (int j = 0; j < m; j++)             scanf("%d", &arr[i][j]);       queue<pair<int, int> > q;       int cnt = 0;     for (int i = 0; i < n; i++)         for (int j = 0; j < m; j++)         {             if (visit[i][j] || !arr[i][j])                 continue;               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 i = 0; i < 8; i++)                 {                     int ny = y + dy[i];                     int nx = x + dx[i];                       if (!(0 <= ny && ny < n) || !(0 <= nx && nx < m) || !arr[ny][nx] || visit[ny][nx])                         continue;                       q.push({ ny,nx });                 }             }         }       cout << cnt;     return 0; } //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus