[1926번] 그림

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 플러드 필

2. BFS

문제 자체의 분류는 플러드 필을 이용하라인데

결국 플러드 필이 BFS 알고리즘과 동일하다 생각하면 된다.

BFS의 기본적인 문제로써 아래 코드를 보면 쉽게 이해가 된다.

(y,x)인 0,0부터 n-1, m-1까지 돌며 1이 발견되면 bfs를 한번 수행시키며 num(그림의 수)를 1증가 시키고

bfs를 돌때 그림의 최대 크기(cnt)를 계속해서 갱신해주면 답을 구할 수 있게 된다.

소스 코드 : 

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>   #define max(a, b)(a > b ? a : b)   using namespace std;   typedef pair<int, int> pii;   int arr[502][502]; bool visit[502][502];   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]);            int ans = 0;     int num = 0;     for(int i = 0 ; i < n ; i ++)         for(int j = 0 ; j < m ; j ++)         {             if (visit[i][j] || !arr[i][j])                 continue;               num++;             queue<pii> q;               q.push(pii(i,j));               int cnt = 0;             while (!q.empty())             {                 int y = q.front().first;                 int x = q.front().second;                   q.pop();                   if (visit[y][x])                     continue;                   cnt++;                 visit[y][x] = true;                   if (y - 1 >= 0 && arr[y - 1][x] && !visit[y - 1][x])                     q.push(pii(y - 1, x));                   if (y + 1 < n && arr[y + 1][x] && !visit[y + 1][x])                     q.push(pii(y + 1, x));                   if (x - 1 >= 0 && arr[y][x - 1] && !visit[y][x - 1])                     q.push(pii(y, x - 1));                   if (x + 1 < m && arr[y][x + 1] && !visit[y][x + 1])                     q.push(pii(y, x + 1));             }               ans = max(ans, cnt);         }       printf("%d\n%d", num, ans);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus